Selon la légende, St. Patrick chassa tous les serpents de Mooland il y a plus de mille ans. Mais les serpents sont revenus ! La Saint-Patrick était le 17 mars, et Bessie veut commémorer St. Patrick en chassant définitivement tous les serpents de Mooland.

Bessie dispose d'un filet pour capturer des serpents répartis en $N$ groupes sur une ligne $(1 \leq N \leq 400)$. Elle doit capturer chaque serpent de chaque groupe dans l'ordre des groupes sur la ligne. Après chaque groupe, elle peut mettre les serpents en cage et commencer le suivant avec un filet vide.

Un filet de taille $s$ permet de capturer un groupe de $g$ serpents si $g \leq s$. Mais capturer un groupe de taille $g$ avec un filet de taille $s$ gaspille $s - g$ d'espace. La taille initiale du filet est libre, et Bessie peut la changer $K$ fois $(1 \leq K < N)$.

Indiquez à Bessie le gaspillage total minimal après la capture de tous les groupes.

Entrée

La première ligne contient $N$ et $K$. La deuxième contient $N$ entiers $a_1,\dots,a_N$, où $a_i$ ($0 \leq a_i \leq 10^6$) est le nombre de serpents du $i$-ième groupe.

Sortie

Affichez un entier donnant le gaspillage minimal après la capture de tous les serpents.

Exemples

Entrée 1

6 2
7 9 8 2 3 2

Sortie 1

3

Remarque

Le filet commence à la taille 7. Après le premier groupe, Bessie le passe à la taille 9 et la conserve jusqu'au 4e groupe, où elle le passe à 3. Le gaspillage total est $(7-7) + (9-9) + (9-8) + (3-2) + (3-3) + (3-2) = 3.$

Auteur du problème : Patrick Zhang