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