Вам заданы массив $$$a_1, a_2, \dots, a_n$$$ и число $$$k$$$.

Вам нужно разделить массив на $$$k$$$ непустых последовательных подотрезков. Каждый элемент в массиве должен быть покрыт ровно одним подотрезком. Пусть $$$f(i)$$$ равно индексу подотрезка, которому принадлежит $$$i$$$-й элемент. Подотрезки нумеруются слева направо и от $$$1$$$ до $$$k$$$.

Тогда цена конкретного разбиения будет равна $$$\sum\limits_{i=1}^{n} (a_i \cdot f(i))$$$. Например, если $$$a = [1, -2, -3, 4, -5, 6, -7]$$$, и мы разделили его на $$$3$$$ подотрезка следующим способом: $$$[1, -2, -3], [4, -5], [6, -7]$$$, тогда цена разбиения будет равна $$$1 \cdot 1 - 2 \cdot 1 - 3 \cdot 1 + 4 \cdot 2 - 5 \cdot 2 + 6 \cdot 3 - 7 \cdot 3 = -9$$$.

Посчитайте максимальную цену, которую вы можете получить, разделив массив $$$a$$$ на $$$k$$$ непустых последовательных подотрезков.