Вам даны массив длины n и число k. Выберем k непересекающихся непустых подотрезков исходного массива. Пусть si — это сумма на i-м слева подотрезке. Посчитайте максимальное возможное значение следующего выражения:
|s1 - s2| + |s2 - s3| + ... + |sk - 1 - sk|Здесь под подотрезком понимается непрерывный подмассив.
Выходные данные
Выведите единственное число — максимальное возможное значения выражения.
Примечание
Рассмотрим первый пример. В оптимальном решении первый подотрезок содержит только первый элемент массива, второй подотрезок состоит из следующих трех, а третий подотрезок содержит только последний элемент массива. Суммы этих подотрезков равны 5, 9 и 1.
Рассмотрим второй пример. Оптимальное решение — взять первые два элемента массива в первый подотрезок, а третий элемент во второй подотрезок. Заметим, что последний элемент массива не входит ни в один подотрезок в этом решении.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 3
5 2 4 3 1
|
12
|
|
2
|
4 2
7 4 3 7
|
8
|