Secondo la leggenda, St. Patrick scacciò tutti i serpenti da Mooland oltre mille anni fa. Ma i serpenti sono tornati! La festa di San Patrizio era il 17 marzo, quindi Bessie vuole commemorare St. Patrick scacciando definitivamente tutti i serpenti da Mooland.

Bessie ha una rete per catturare serpenti distribuiti in $N$ gruppi lungo una linea $(1 \leq N \leq 400)$. Deve catturare tutti i serpenti di ogni gruppo nell'ordine dei gruppi lungo la linea. Dopo ogni gruppo può mettere i serpenti in una gabbia e iniziare il successivo con la rete vuota.

Una rete di dimensione $s$ può catturare un gruppo di $g$ serpenti se $g \leq s$. Ma catturare un gruppo di dimensione $g$ con una rete di dimensione $s$ spreca $s - g$ spazio. La dimensione iniziale è libera e Bessie può cambiarla $K$ volte $(1 \leq K < N)$.

Dì a Bessie il minimo spazio totale sprecato dopo aver catturato tutti i gruppi.

Input

La prima riga contiene $N$ e $K$. La seconda contiene $N$ interi $a_1,\dots,a_N$, dove $a_i$ ($0 \leq a_i \leq 10^6$) è il numero di serpenti nel gruppo $i$.

Output

Stampa un intero che indica il minimo spazio sprecato dopo la cattura di tutti i serpenti.

Esempi

Input 1

6 2
7 9 8 2 3 2

Output 1

3

Spiegazione

La rete inizia con dimensione 7. Dopo il primo gruppo, Bessie passa a 9 e mantiene tale dimensione fino al quarto gruppo, quando passa a 3. Lo spazio totale sprecato è $(7-7) + (9-9) + (9-8) + (3-2) + (3-3) + (3-2) = 3.$

Autore del problema: Patrick Zhang