На вулиці є \(n\) будинків з номерами \(1,2,…,n\). Відстань між будинками \(a\) і \(b\) дорівнює \(∣a−b∣\). Ви знаєте кількість дітей у кожному будинку.

Ваше завдання створити \(k\) шкіл таким чином, щоб кожна школа була в якомусь будинку. Потім кожна дитина йде до найближчої школи. Яка мінімальна загальна пройдена відстань дітей, якщо ви будете діяти оптимально?

Обмеження

• \( 1≤k≤n≤3000\)
• \( 1≤c_i ​ ≤10^9\)

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

У першому рядку є два цілі числа \(n\) і \(k\): кількість будинків і кількість шкіл. Будинки пронумеровані \(1,2…,n\).

Після цього є \(n\) цілих чисел \(c_1 ​ ,c_2 ​ ,…,c_n\) ​ : кількість дітей у кожному будинку.

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

Вивести шукану мінімальну загальну відстань.

Пояснення:

у будинках 2 і 5 слід розмістити школи.

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

6 2
2 7 1 4 6 4

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

11