Según la leyenda, St. Patrick expulsó a todas las serpientes de Mooland hace más de mil años. ¡Pero han regresado! El día de San Patricio fue el 17 de marzo, así que Bessie lo conmemorará expulsando de una vez por todas a las serpientes de Mooland.

Bessie tiene una red para capturar serpientes distribuidas en $N$ grupos sobre una línea $(1 \leq N \leq 400)$. Debe capturar todas las serpientes de cada grupo en el orden de los grupos. Tras capturar un grupo puede poner las serpientes en una jaula y comenzar el siguiente con la red vacía.

Una red de tamaño $s$ permite capturar un grupo de $g$ serpientes si $g \leq s$. Pero capturar un grupo de tamaño $g$ con una red de tamaño $s$ desperdicia $s - g$ de espacio. La red puede comenzar con cualquier tamaño y Bessie puede cambiarlo $K$ veces $(1 \leq K < N)$.

Indica a Bessie el mínimo espacio total desperdiciado tras capturar todos los grupos.

Entrada

La primera línea contiene $N$ y $K$. La segunda contiene $N$ enteros $a_1,\dots,a_N$, donde $a_i$ ($0 \leq a_i \leq 10^6$) es la cantidad de serpientes del grupo $i$.

Salida

Imprime un entero: el mínimo espacio desperdiciado tras capturar todas las serpientes.

Ejemplos

Entrada 1

6 2
7 9 8 2 3 2

Salida 1

3

Nota

La red comienza con tamaño 7. Después del primer grupo, Bessie lo cambia a 9 y lo conserva hasta el cuarto grupo, cuando lo cambia a 3. El espacio total desperdiciado es $(7-7) + (9-9) + (9-8) + (3-2) + (3-3) + (3-2) = 3.$

Autor del problema: Patrick Zhang