Segundo a lenda, St. Patrick expulsou todas as cobras de Mooland há mais de mil anos. Mas elas voltaram! O dia de São Patrício foi em 17 de março, então Bessie vai homenagear St. Patrick expulsando todas as cobras de Mooland de uma vez por todas.

Bessie tem uma rede para capturar cobras distribuídas em $N$ grupos em uma linha $(1 \leq N \leq 400)$. Ela deve capturar todas as cobras de cada grupo na ordem dos grupos na linha. Após cada captura, pode colocar as cobras numa gaiola e começar o próximo grupo com a rede vazia.

Uma rede de tamanho $s$ captura um grupo de $g$ cobras se $g \leq s$. Porém, capturar um grupo de tamanho $g$ com uma rede de tamanho $s$ desperdiça $s - g$ de espaço. O tamanho inicial da rede é livre, e Bessie pode mudá-lo $K$ vezes $(1 \leq K < N)$.

Diga a Bessie o menor espaço total desperdiçado após capturar todos os grupos.

Entrada

A primeira linha contém $N$ e $K$. A segunda contém $N$ inteiros $a_1,\dots,a_N$, onde $a_i$ ($0 \leq a_i \leq 10^6$) é o número de cobras no grupo $i$.

Saída

Imprima um inteiro que indique o menor espaço desperdiçado após capturar todas as cobras.

Exemplos

Entrada 1

6 2
7 9 8 2 3 2

Saída 1

3

Nota

A rede começa com tamanho 7. Após o primeiro grupo, Bessie muda para 9 e mantém esse tamanho até o quarto grupo, quando muda para 3. O espaço total desperdiçado é $(7-7) + (9-9) + (9-8) + (3-2) + (3-3) + (3-2) = 3.$

Autor do problema: Patrick Zhang