Стовпчики

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

Перший рядок містить два цілі числа $n$ та $k$ ($1\le n\le 3\cdot 10^3$, $0\le k\le n$).

Другий рядок містить $n$ цілих чисел $a_1,a_2,\dots ,a_n$ ($0\le a_i\le 10^9$).

Output

Виведіть одне ціле число — відповідь на задачу.

Examples

Scoring

Рішення, які правильно працюють для $k=0$ та $n\le 250$, отримають принаймні $40$ балів.

Рішення, які правильно працюють для $n\le 250$, отримають принаймні $85$ балів.