뱀

전설에 따르면 천 년도 더 전에 성 패트릭이 물랜드의 뱀을 모두 쫓아냈다고 한다. 하지만 그동안 뱀들이 다시 물랜드로 돌아왔다! 성 패트릭의 날은 3월 17일이므로, 베시는 성 패트릭을 기념해 물랜드의 뱀을 완전히 몰아내려 한다.

베시는 직선 위에 $N$개의 그룹으로 나뉘어 있는 뱀을 잡을 그물을 가지고 있다 $(1 \leq N \leq 400)$. 베시는 직선에 나타난 순서대로 모든 그룹의 모든 뱀을 잡아야 한다. 그룹 하나를 잡을 때마다 뱀을 우리에 넣고, 다음 그룹을 위해 빈 그물로 시작할 수 있다.

크기 $s$인 그물로는 뱀이 $g$마리 들어 있는 그룹을 잡을 수 있다. 단, $g \leq s$여야 한다. 다만 베시가 크기 $s$인 그물로 크기 $g$인 뱀 그룹을 잡을 때마다 $s - g$만큼의 공간이 낭비된다. 베시의 그물은 어떤 크기로든 시작할 수 있고, 그물의 크기를 $K$번 바꿀 수 있다 $(1 \leq K < N)$.

모든 그룹을 잡은 뒤 누적되는 낭비된 공간의 총량의 최솟값을 베시에게 알려주자.

첫째 줄에 $N$과 $K$가 주어진다. 둘째 줄에 $N$개의 정수 $a\_1,\dots,a\_N$이 주어지며, $a\_i$ ($0 \leq a\_i \leq 10^6$)는 $i$번째 그룹에 있는 뱀의 수이다.

베시가 모든 뱀을 잡은 뒤 낭비된 공간의 최솟값을 정수 하나로 출력한다.

베시의 그물은 크기 7로 시작한다. 첫 번째 뱀 그룹을 잡은 뒤 그물 크기를 9로 바꾸고, 네 번째 뱀 그룹에 이르기까지 그 크기를 유지하다가 그물 크기를 3으로 바꾼다. 낭비된 공간의 총량은 $(7-7) + (9-9) + (9-8) + (3-2) + (3-3) + (3-2) = 3$이다.