K блоків

Вам надано послідовність A з n додатних цілих чисел. Значенням розбиття послідовності на k блоків називається сума максимумів у кожному з цих k блоків. Ваше завдання — знайти таке розбиття, яке має мінімальне значення для заданого числа k.

Вхідні дані

У першому рядку містяться два цілі числа n і k (1 ≤ n ≤ 10^5, 1 ≤ k ≤ min(n, 100)). У другому рядку наведено n цілих чисел A[1], A[2], ..., A[n] (1 ≤ A[i] ≤ 10^6) — елементи послідовності.

Вихідні дані

Виведіть одне число — значення мінімального розбиття.

Приклади