K блоків#7473
Вам надано послідовність з додатних цілих чисел. Значенням розбиття послідовності на блоків називається сума максимумів у кожному з цих блоків. Ваше завдання — знайти таке розбиття, яке має мінімальне значення для заданого числа .
У першому рядку містяться два цілі числа і (1 \le n \le 10^5, 1 \le k \le \min(n, 100)). У другому рядку наведено цілих чисел A_1, A_2, \ldots, A_n (1 \le A_i \le 10^6) — елементи послідовності.
Виведіть одне число — значення мінімального розбиття.
Приклад 1
Приклад 2