Змеи
Согласно легенде, Святой Патрик изгнал всех змей в Муленде более тысячи лет назад. Однако с тех пор змеи вернулись в Муленд! День Святого Патрика был 17 марта, поэтому Бесси собирается почтить память Святого Патрика, изгнав всех змей из Муленда раз и навсегда.
Бесси оснащена сетью для ловли змей, расположенных в n группах на прямой. Бесси должна поймать каждую змею в каждой группе в том порядке, в котором группы появляются на линии. Каждый раз, когда Бесси захватывает группу, она может поместить змей в клетку и начать с пустой сети для следующей группы.
Сеть размером s означает, что Бесси может поймать любую группу, содержащую g змей, где g ≤ s. Однако каждый раз, когда Бесси ловит группу змей размера g сеткой s, она не использует s - g пространства. Сеть Бесси может начинаться с любого размера, и она может изменить размер своей сети k раз.
Определите для Бесси минимальное количество потраченного впустую пространства, которое она может накопить после захвата всех групп.
Входные данные
Первая строка содержит числа n (1 ≤ n ≤ 400) и k (1 ≤ k < n). Вторая строка содержит n целых чисел a[1], ..., a[n], где a[i] (0 ≤ a[i] ≤ 10^6) количество змей в i-ой группе.
Выходные данные
Выведите одно целое число - минимальное количество потраченного впустую пространства после того, как Бесси поймает всех змей.
Пример
Сеть Бесси начинается с размера 7. После того, как она поймает первую группу змей, она меняет размер сети на 9 и сохраняет этот размер до 4 -ой группы змей, когда она меняет сеть на размер 3. Общее потраченное впустую пространство составляет (7 − 7) + (9 − 9) + (9 − 8) + (3 − 2) + (3 − 3) + (3 − 2) = 3.