G. Очередная задача на разбиения
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задан массив $$$a_1, a_2, \dots, a_n$$$. Вам необходимо разделить его на $$$k$$$ подотрезков (так, что каждый элемент принадлежит ровно одному подотрезку).

Весом подотрезка $$$a_l, a_{l+1}, \dots, a_r$$$ назовем значение $$$(r - l + 1) \cdot \max\limits_{l \le i \le r}(a_i)$$$. Весом разбиения — суммарный вес его подотрезков.

Найдите разбиение минимального веса.

Входные данные

В первой строке заданы два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le n \le 2 \cdot 10^4$$$, $$$1 \le k \le \min(100, n)$$$) — длина массива $$$a$$$ и количество подотрезков в разбиении.

Во второй строке заданы $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 2 \cdot 10^4$$$) — массив $$$a$$$.

Выходные данные

Выведите единственное число — минимальный вес среди всех возможных разбиений.

Примеры
Входные данные
4 2
6 1 7 4
Выходные данные
25
Входные данные
4 3
6 1 7 4
Выходные данные
21
Входные данные
5 4
5 1 5 1 5
Выходные данные
21
Примечание

Оптимальное разбиение в первом примере: $$$6$$$ $$$1$$$ $$$7$$$ $$$\bigg|$$$ $$$4$$$.

Оптимальное разбиение во втором примере: $$$6$$$ $$$\bigg|$$$ $$$1$$$ $$$\bigg|$$$ $$$7$$$ $$$4$$$.

Одно из оптимальных разбиений в третьем примере: $$$5$$$ $$$\bigg|$$$ $$$1$$$ $$$5$$$ $$$\bigg|$$$ $$$1$$$ $$$\bigg|$$$ $$$5$$$.