Змії#10322
Згідно з легендою, Святий Патрик вигнав усіх змій з Муленда понад тисячу років тому. Однак з тих пір змії повернулися! День Святого Патрика був 17 березня, і Бессі вирішила вшанувати його пам'ять, вигнавши всіх змій з Муленда раз і назавжди.
Бессі має сітку для ловлі змій, які розташовані у групах на прямій лінії. Їй потрібно зловити кожну змію в кожній групі в тому порядку, в якому групи з'являються на лінії. Кожного разу, коли Бессі ловить групу, вона може помістити змій у клітку і почати з порожньою сіткою для наступної групи.
Сітка розміром дозволяє Бессі зловити будь-яку групу, що містить змій, де g \leq s. Однак, коли Бессі ловить групу змій розміру сіткою , вона не використовує s - g простору. Бессі може почати з сіткою будь-якого розміру і може змінити розмір своєї сітки разів.
Визначте для Бессі мінімальну кількість невикористаного простору, яке вона може накопичити після захоплення всіх груп.
Перший рядок містить числа (1 \leq n \leq 400) і (1 \leq k < n). Другий рядок містить цілих чисел a_1, \ldots, a_n, де a_i (0 \leq a_i \leq 10^6) — кількість змій у -ій групі.
Виведіть одне ціле число — мінімальну кількість невикористаного простору після того, як Бессі зловить усіх змій.
\begin{example}\exmp{6 27 9 8 2 3 2}{3}%\end{example}
Приклад 1
Сітка Бессі починається з розміру . Після того, як вона зловить першу групу змій, вона змінює розмір сітки на і зберігає цей розмір до -ої групи змій, коли вона змінює сітку на розмір . Загальний невикористаний простір становить (7 - 7) + (9 - 9) + (9 - 8) + (3 - 2) + (3 - 3) + (3 - 2) = .