Задачи
Стовпчики
Стовпчики
Дано поле розміром $10^9 \times n$. Тобто з $10^9$ рядками та $n$ стовпчиками. Рядки нумеруються знизу вгору від $1$ до $10^9$, а стовпчики зліва направо з $1$ до $n$.
Відомо, що в $i$-му стовпчику перші $a_i$ клітинки знизу (тобто клітинки від $1$ до $a_i$) потрібно зафарбувати. За одну операцію фарбування ви можете вибрати будь-яку послідовну кількість клітин в одному рядку і зафарбувати їх всі. Зверніть увагу, що ви не можете фарбувати клітини, які фарбувати непотрібно. Ви також не можете фарбувати одну й ту ж клітину більше одного разу.
Перед виконанням цих операцій ви можете змінити $k$ значень $a_i$ на будь-які числа від $0$ до $10^9$. Ці числа не обов'язково мають бути однаковими.
Знайдіть мінімальну кількість операцій, які потрібно виконати, щоб зафарбувати всі потрібні клітини.
\InputFile
Перший рядок містить два цілі числа $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$).
\OutputFile
Виведіть одне ціле число --- відповідь на задачу.
\Scoring
Рішення, які правильно працюють для $k=0$ та $n \leq 250$, отримають принаймні $40$ балів.
Рішення, які правильно працюють для $n \leq 250$, отримають принаймні $85$ балів.
Входные данные #1
5 0 3 2 1 2 3
Выходные данные #1
5
Входные данные #2
5 1 3 2 1 2 3
Выходные данные #2
4
Входные данные #3
7 3 4 7 2 4 5 0 4
Выходные данные #3
5