Змії
Згідно з легендою, Святий Патрик вигнав усіх змій з Муленда понад тисячу років тому. Однак з тих пір змії повернулися! День Святого Патрика був 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.