29126번 - Диаграмма 다국어

Зайдя в спальню Вилли и Кейт, Альф случайно заметил свернутый лист бумаги. Пришелец не смог удержать желания буквально засунуть свой нос в этот сверток. Развернув его, он обнаружил, что на листе изображена какая-то диаграмма. Альф сразу же понял, что эта диаграмма принадлежит Вилли и незамедлительно решил ее исправить. Диаграмма представляет из себя набор столбцов разной высоты. Пришельцу не понравилось то, что на картинке присутствует огромное количество перепадов высоты. Он решил уменьшить это количество, уменьшив или увеличив высоты некоторых столбцов. В итоге он хочет получить диаграмму, на которой не больше $k$ перепадов. Представим диаграмму как массив $a_i$, где каждый элемент обозначает высоту $i$-го столбца. Количество перепадов опеределяется как количество соседних столбцов, высоты которых различаются. Однако Альф, как заботливый пришелец, хочет сделать так, чтобы разница между исходной диаграммой и новой была минимальной. Разница между диаграммами определяется как $\sum_{i=1}^n |a_i-b_i|$, где $a_i$ и $b_i$ обозначают высоты столбцов диаграмм. Помогите Альфу найти минимальную разницу между исходной диаграммой и диаграммой, в которой не больше $k$ перепадов высот.

В первой строке входного файла даны два числа $n$ и $k$ ($1 \le n \le 1000, 0 \le k \le 100$) --- количество столбцов в диаграмме и максимальное количество перепадов высот. Во второй строке дано $n$ чисел $a_i$ ($0 \le a_i \le 10^9$) --- описание высот столбцов.

Выведите ответ на задачу.