Дано поле розміром $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$ балів.