Вам задан массив \(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\).
Выведите единственное число — минимальный вес среди всех возможных разбиений.
Оптимальное разбиение в первом примере: \(6\) \(1\) \(7\) \(\bigg|\) \(4\).
Оптимальное разбиение во втором примере: \(6\) \(\bigg|\) \(1\) \(\bigg|\) \(7\) \(4\).
Одно из оптимальных разбиений в третьем примере: \(5\) \(\bigg|\) \(1\) \(5\) \(\bigg|\) \(1\) \(\bigg|\) \(5\).
4 2 6 1 7 4
25
4 3 6 1 7 4
21
5 4 5 1 5 1 5
5000 ms 512 Mb Правила оформления программ и список ошибок при автоматической проверке задач