Стовпчики
Стовпчики
Дано поле розміром 10^9 \times n. Тобто з 10^9 рядками та n стовпчиками. Рядки нумеруються знизу вгору від 1 до 10^9, а стовпчики зліва направо з 1 до n.
Відомо, що в i-му стовпчику перші a_i клітинки знизу (тобто клітинки від 1 до a_i) потрібно зафарбувати. За одну операцію фарбування ви можете вибрати будь-яку послідовну кількість клітин в одному рядку і зафарбувати їх всі. Зверніть увагу, що ви не можете фарбувати клітини, які фарбувати непотрібно. Ви також не можете фарбувати одну й ту ж клітину більше одного разу.
Перед виконанням цих операцій ви можете змінити k значень a_i на будь-які числа від 0 до 10^9. Ці числа не обов'язково мають бути однаковими.
Знайдіть мінімальну кількість операцій, які потрібно виконати, щоб зафарбувати всі потрібні клітини.
Input data
Перший рядок містить два цілі числа n та k (1 \leq n \leq 3 \cdot 10^3, 0 \leq k \leq n).
Другий рядок містить n цілих чисел a_1, a_2, \dots, a_n (0 \leq a_i \leq 10^9).
Output data
Виведіть одне ціле число — відповідь на задачу.
Examples
5 0 3 2 1 2 3
5
5 1 3 2 1 2 3
4
7 3 4 7 2 4 5 0 4
5
Scoring
Рішення, які правильно працюють для k=0 та n \leq 250, отримають принаймні 40 балів.
Рішення, які правильно працюють для n \leq 250, отримають принаймні 85 балів.