Według legendy St. Patrick wypędził wszystkie węże z Mooland ponad tysiąc lat temu. Jednak węże wróciły! Dzień Świętego Patryka był 17 marca, więc Bessie zamierza uczcić St. Patrick, wypędzając wszystkie węże z Mooland raz na zawsze.

Bessie ma sieć do łapania węży rozłożonych w $N$ grupach na prostej $(1 \leq N \leq 400)$. Musi złapać każdego węża w każdej grupie w kolejności grup na prostej. Po każdej grupie może włożyć węże do klatki i zacząć następną z pustą siecią.

Sieć rozmiaru $s$ może złapać grupę $g$ węży, jeśli $g \leq s$. Jednak złapanie grupy rozmiaru $g$ siecią rozmiaru $s$ marnuje $s - g$ miejsca. Początkowy rozmiar jest dowolny, a Bessie może zmienić rozmiar $K$ razy $(1 \leq K < N)$.

Podaj Bessie minimalną sumę zmarnowanego miejsca po złapaniu wszystkich grup.

Wejście

Pierwszy wiersz zawiera $N$ i $K$. Drugi zawiera $N$ liczb całkowitych $a_1,\dots,a_N$, gdzie $a_i$ ($0 \leq a_i \leq 10^6$) to liczba węży w $i$-tej grupie.

Wyjście

Wypisz jedną liczbę całkowitą: minimalne zmarnowane miejsce po złapaniu wszystkich węży.

Przykład

Wejście 1

6 2
7 9 8 2 3 2

Wyjście 1

3

Uwagi

Początkowy rozmiar sieci to 7. Po pierwszej grupie Bessie zmienia go na 9 i zachowuje aż do czwartej grupy, przy której zmienia go na 3. Łączne zmarnowane miejsce wynosi $(7-7) + (9-9) + (9-8) + (3-2) + (3-3) + (3-2) = 3.$

Autor zadania: Patrick Zhang