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