У Беси есть сеть ловить змеек, распределённых в \(N\) групп на линии \((1 \leq N \leq 400)\).
Беси должна поймать каждую змейку в каждой группе. Каждый раз, когда Беси ловит группу
она может переложить змеек в клетку и начать пустой сеткой ловить следующую группу.
Сеть размером \(s\) означает, что Беси может поймать любую группу, которая
содержит \(g\) змеек, где \(g \leq s\). Однако каждый раз, когда Беси ловит группу змеек размером
\(g\) сетью размером \(s\), она тратит впустую \(s - g\) пространства. Беси может начинать с сети
любого размера и Беси может изменять размер своей сети \(K\) раз \((1 \leq K < N)\).
Выведите минимальное количество потерянного пространства, которого может добиться
Беси после вылавливания всех групп змеек.
ФОРМАТ ВВОДА (файл snakes.in):
Первая строка содержит \(N\) и \(K\). Вторая строка содержит \(N\) целых чисел
\(a_1,\dots,a_N\), где \(a_i\) (\(0 \leq a_i \leq 10^6\)) количество змеек в \(i\)-ой группе.
ФОРМАТ ВЫВОДА (файл snakes.out):
Выведите одно целое число - минимальное количество потерянного пространства
после того как Беси выловит всех змеек.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6 2
7 9 8 2 3 2
|
3
|