eolymp
bolt
Try our new interface for solving problems
Problems

Стовпчики

Стовпчики

Time limit 15 seconds
Memory limit 1024 MiB

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

Перший рядок містить два цілі числа 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).

Output data

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

Examples

Input example #1
5 0
3 2 1 2 3
Output example #1
5
Input example #2
5 1
3 2 1 2 3
Output example #2
4
Input example #3
7 3
4 7 2 4 5 0 4
Output example #3
5

Scoring

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

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

Author Anton Tsypko
Source Всеукраїнська юніорська та дівоча олімпіади з інформатики 2021-2022, Перший відбірковий тур