2018 учебный год

(Тиманың бапкерлік таңдауы)

Ограничение по времени:

4 seconds

Ограничение по памяти:

256 megabytes

Жақын уақыттан бері Тима баскетбол командасын жаттықтыруды бастады. Команданың капитаны ретінде әрқашан бойы ең ұзын ойыншы таңдалады. Ол команданың сәйкес келмеушілік формуласын ойлап тапты. Команданың сәйкес келмеушілігі оның капитатының бойымен қалғандарының бойының айырмаларының қосындысы. Анықтап айтсақ, $h_1, h_2, ... , h_m$ — командадағы ойыншылардың бойларының ұзындығы болсын, $mx = max(h_1, h_2, ..., h_m)$, онда сәйкес келмеушілік = $\sum_{i=1}^{m} mx$-$h_i$. Тимада бір ретте тұрған $n$ ойыншы бар, $i$-ші ойыншының бойы $a_i$. Ол барлық ойыншыны $k$ командаға бөлгісі келеді, әр ойыншы бір командада болу керек және әр команда ретте қатар тұрған ойыншылардан құралуы керек. Тима барлық команданың сәйкес келмеушіліктерінің қосынды аз болатындай бөлгісі келеді. Тимаға командаларды қолайлы бөлуге көмектесіңіз.

Формат входного файла

Бірінші жолда екі бүтін сан берілген $n$ және $k$ ($1 \le n \le 10^5$, $1 \le k \le min(n, 20)$) — ойыншылардың саны және командалардың саны. Екінші жолда $n$ бүтін $a_i$ ($1 \le a_i \le 10^6$) — қатардың сол жағынан $i$-ші тұрған ойыншының бойының ұзындығы.

Формат выходного файла

Жалғыз бүтін сан шығарыңыз — есептің жауабын.

Система оценки

Есеп алты бөлімнен тұрады, әр бөлімде есептің берілгендегі шарртар орындалады және:

1. $n \le 100$, $k = 1$. Бөлім $5$ ұпайға бағаланады.
2. $n \le 2000$. Бөлім $11$ ұпайға бағаланады.
3. $k = 2$. Бөлім $8$ ұпайға бағаланады.
4. $k = 3$. Бөлім $15$ ұпайға бағаланады.
5. $a_i \le a_{i+1}$, барлық $1 \le i < n$ үшін. Бөлім $19$ ұпайға бағаланады.
6. Есептің еңгізу форматындағы шарттар орындалады. Бөлім $42$ ұпайға бағаланады.

Пример:

s Вход

7 3
6 4 1 5 3 2 2

Ответ

7

Вход

5 2
4 1 5 5 6

Ответ

5

Вход

9 2
3 7 4 1 3 2 4 6 7

Ответ

22

( Temirlan Satylkhanov )