Согласно легенде, более тысячи лет назад St. Patrick изгнал всех змей из Mooland. Но с тех пор змеи вернулись! День святого Патрика был 17 марта, поэтому Bessie собирается почтить St. Patrick, раз и навсегда изгнав всех змей из Mooland.

У Bessie есть сеть для ловли змей, расположенных $N$ группами на прямой $(1 \leq N \leq 400)$. Она должна поймать всех змей в каждой группе в порядке расположения групп. После каждой группы она может положить змей в клетку и начать следующую с пустой сетью.

Сеть размера $s$ позволяет поймать группу из $g$ змей, где $g \leq s$. Однако при ловле группы размера $g$ сетью размера $s$ теряется $s - g$ места. Начальный размер сети произволен, и Bessie может менять её размер $K$ раз $(1 \leq K < N)$.

Сообщите Bessie минимальную суммарную потерю места после ловли всех групп.

Входные данные

Первая строка содержит $N$ и $K$. Вторая содержит $N$ целых чисел $a_1,\dots,a_N$, где $a_i$ ($0 \leq a_i \leq 10^6$) — число змей в $i$-й группе.

Выходные данные

Выведите одно целое число — минимальную потерю места после ловли всех змей.

Примеры

Входные данные 1

6 2
7 9 8 2 3 2

Выходные данные 1

3

Примечание

Начальный размер сети равен 7. Поймав первую группу, Bessie меняет размер на 9 и сохраняет его до 4-й группы, когда меняет на 3. Суммарная потеря места равна $(7-7) + (9-9) + (9-8) + (3-2) + (3-3) + (3-2) = 3.$

Автор задачи: Patrick Zhang