전설에 따르면 천 년도 더 전에 St. Patrick은 Mooland의 모든 뱀을 쫓아냈습니다. 하지만 뱀들이 돌아왔습니다! 성 패트릭의 날은 3월 17일이었으므로 Bessie는 Mooland의 모든 뱀을 완전히 쫓아내어 St. Patrick을 기념하려 합니다.

Bessie는 일직선 위의 $N$개 무리에 분포한 뱀을 잡을 그물을 가지고 있습니다 $(1 \leq N \leq 400)$. 무리가 줄에 나타나는 순서대로 각 무리의 모든 뱀을 잡아야 합니다. 한 무리를 잡을 때마다 뱀을 우리에 넣고 빈 그물로 다음 무리를 잡을 수 있습니다.

크기 $s$인 그물은 $g \leq s$일 때 $g$마리의 뱀이 있는 무리를 잡을 수 있습니다. 하지만 크기 $g$인 무리를 크기 $s$인 그물로 잡을 때마다 $s - g$의 공간이 낭비됩니다. 초기 그물 크기는 자유롭게 정할 수 있으며 Bessie는 크기를 $K$번 바꿀 수 있습니다 $(1 \leq K < N)$.

모든 무리를 잡은 뒤 누적되는 낭비 공간의 총합의 최솟값을 Bessie에게 알려 주세요.

입력

첫 줄은 $N$과 $K$를 포함합니다. 둘째 줄은 $N$개의 정수 $a_1,\dots,a_N$을 포함하며, $a_i$($0 \leq a_i \leq 10^6$)는 $i$번째 무리의 뱀 수입니다.

출력

모든 뱀을 잡은 뒤 낭비한 공간의 최솟값을 나타내는 정수 하나를 출력하세요.

예제

입력 1

6 2
7 9 8 2 3 2

출력 1

3

참고

처음 그물 크기는 7입니다. 첫 무리를 잡은 뒤 9로 바꾸고 넷째 무리까지 유지하다가 그 무리에서 3으로 바꿉니다. 낭비 공간의 총합은 $(7-7) + (9-9) + (9-8) + (3-2) + (3-3) + (3-2) = 3.$입니다.

문제 작성자: Patrick Zhang