캐시백

당신은 최고의 Wraith King이므로, Vinnytsia 중심부의 Nizhniy Magazin «Mir»에서 할인을 제공한다.

길이가 n인 배열 a와 정수 c가 주어진다.

길이가 k인 어떤 배열 b의 값은 가장 작은 개 원소를 제외한 나머지 원소의 합이다. 예를 들어, c = 2일 때 배열 $[3, 1, 6, 5, 2]$의 값은 3 + 6 + 5 = 14이다.

a를 연속한 부분 배열들로 나누는 가능한 모든 분할 중에서, 이 부분 배열들의 값의 합으로 가능한 최솟값을 출력한다.

첫째 줄에 정수 n와 c가 주어진다. (1 ≤ n, c ≤ 100 000).

둘째 줄에 a의 원소인 n개의 정수 ai가 주어진다. (1 ≤ ai ≤ 109)

a의 어떤 분할을 이루는 부분 배열들의 값의 합으로 가능한 최솟값을 나타내는 정수 하나를 출력한다.

첫 번째 예제에서는 어떤 분할을 선택해도 합이 6이 된다.

두 번째 예제에서 최적 분할 중 하나는 $[1, 1]$, $[10, 10, 10, 10, 10, 10, 9, 10, 10, 10]$이며, 각각의 값은 2와 90이다.

세 번째 예제에서 최적 분할 중 하나는 $[2, 3]$, $[6, 4, 5, 7]$, $[1]$이며, 각각의 값은 3, 13, 1이다.

네 번째 예제에서 최적 분할 중 하나는 $[1]$, $[3, 4, 5, 5, 3, 4]$, $[1]$이며, 각각의 값은 1, 21, 1이다.