Der Legende nach vertrieb St. Patrick vor über tausend Jahren alle Schlangen aus Mooland. Doch die Schlangen sind zurückgekehrt! Der St.-Patrick-Tag war am 17. März, deshalb will Bessie St. Patrick ehren, indem sie alle Schlangen endgültig aus Mooland vertreibt.

Bessie hat ein Netz, um die in $N$ Gruppen auf einer Linie verteilten Schlangen zu fangen $(1 \leq N \leq 400)$. Sie muss alle Schlangen jeder Gruppe in der Reihenfolge der Gruppen auf der Linie fangen. Nach jeder Gruppe kann sie die Schlangen in einen Käfig legen und die nächste Gruppe mit einem leeren Netz beginnen.

Ein Netz der Größe $s$ kann eine Gruppe mit $g$ Schlangen fangen, wenn $g \leq s$. Doch eine Gruppe der Größe $g$ mit einem Netz der Größe $s$ zu fangen verschwendet $s - g$ Platz. Die Anfangsgröße ist frei wählbar, und Bessie kann die Netzgröße $K$ Mal ändern $(1 \leq K < N)$.

Bestimme für Bessie den minimalen insgesamt verschwendeten Platz nach dem Fang aller Gruppen.

Eingabe

Die erste Zeile enthält $N$ und $K$. Die zweite enthält $N$ ganze Zahlen $a_1,\dots,a_N$, wobei $a_i$ ($0 \leq a_i \leq 10^6$) die Schlangenzahl der $i$-ten Gruppe ist.

Ausgabe

Gib eine ganze Zahl aus: den minimalen verschwendeten Platz nach dem Fang aller Schlangen.

Beispiele

Eingabe 1

6 2
7 9 8 2 3 2

Ausgabe 1

3

Hinweis

Das Netz beginnt mit Größe 7. Nach der ersten Gruppe ändert Bessie die Größe auf 9 und behält sie bis zur vierten Gruppe, bei der sie auf 3 wechselt. Der insgesamt verschwendete Platz beträgt $(7-7) + (9-9) + (9-8) + (3-2) + (3-3) + (3-2) = 3.$

Aufgabenautor: Patrick Zhang