«Ланністер завжди платить за боргами».

Це правда, тепер у вас є шанс отримати гроші від Хайме Ланністера.

В армії Хайме всього \(N\) воїнів. І всі вони стоять в один ряд.

Тепер Хайме хоче передати повідомлення своїм воїнам. Але дуже важко передати повідомлення, якщо воїни стоять в один ряд. Отже, Хайме хоче розбити цей єдиний рядок на \(K\) рядків. Так, щоб у кожному ряду був хоча б один воїн.

Крім того, існує кількість нещастя, пов’язана з кожним воїном \(x\), яка дорівнює: кількості воїнів перед \(x\) (у його ряду), чий зріст більший за зріст \(x\). А повне нещастя — це сума нещастя всіх воїнів.

Хайме хоче, щоб його армія була щаслива якомога більше.

Тепер Хайме хоче, щоб ви розбили один рядок на \(K\) рядків, щоб загальне нещастя було мінімальним.

Примітка: вам потрібно просто розірвати ряд, вам не дозволяється змінювати положення воїнів.

Формат вхідних даних

Перший рядок містить два цілі числа \(N\) & \(K\).

Другий рядок містить \(N\) цілих чисел, \(i\)-те з яких позначає зріст \(i\)-го воїна, що стоїть у цьому єдиному ряду (представлений як \(H[i]\)).

Обмеження

• \(1 \le N \le 5000\)
• \(1 \le K \le N\)
• \(1 \le H[i] \le 10^5\)  

Формат вихідних даних

Виведіть мінімально можливе значення "повного нещастя".

Приклад вхідних даних

6 3
20 50 30 60 40 100

Приклад вихідних даних

0

Розірвати:

• 1 ряд: 20 50
• 2 ряд: 30 60
• 3 ряд: 40 100

Приклад вхідних даних

8 3
20 50 30 60 40 100 5 1

Приклад вихідних даних

2

• Ряд 1 : 20 50 30 60, Нещастя = 1
• Ряд 2: 40 100, Нещастя = 0
• Ряд 3 : 5 1, Нещастя = 1
• Всього = 2