Вам заданы массив \(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\) непустых последовательных подотрезков.
Выходные данные
Выведите максимальную цену, которую вы можете получить, разделив массив \(a\) на \(k\) непустых последовательных подотрезков.