Дано поле розміром 109×n. Тобто з 109 рядками та n стовпчиками. Рядки нумеруються знизу вгору від 1 до 109, а стовпчики зліва направо з 1 до n.
Відомо, що в i-му стовпчику перші ai клітинки знизу (тобто клітинки від 1 до ai) потрібно зафарбувати. За одну операцію фарбування ви можете вибрати будь-яку послідовну кількість клітин в одному рядку і зафарбувати їх всі. Зверніть увагу, що ви не можете фарбувати клітини, які фарбувати непотрібно. Ви також не можете фарбувати одну й ту ж клітину більше одного разу.
Перед виконанням цих операцій ви можете змінити k значень ai на будь-які числа від 0 до 109. Ці числа не обов'язково мають бути однаковими.
Знайдіть мінімальну кількість операцій, які потрібно виконати, щоб зафарбувати всі потрібні клітини.
Перший рядок містить два цілі числа n та k (1≤n≤3⋅103, 0≤k≤n).
Другий рядок містить n цілих чисел a1,a2,…,an (0≤ai≤109).
Виведіть одне ціле число — відповідь на задачу.
Рішення, які правильно працюють для k=0 та n≤250, отримають принаймні 40 балів.
Рішення, які правильно працюють для n≤250, отримають принаймні 85 балів.