E2. Разрезание массива
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам даны массив длины n и число k. Выберем k непересекающихся непустых подотрезков исходного массива. Пусть si — это сумма на i-м слева подотрезке. Посчитайте максимальное возможное значение следующего выражения:

|s1 - s2| + |s2 - s3| + ... + |sk - 1 - sk|

Здесь под подотрезком понимается непрерывный подмассив.

Входные данные

Первая строка входных данных содержит два целых числа n и k. Вторая строка содержит n целых чисел — элементы массива. Каждый из элементов массива не превосходит 104 по модулю.

Задача состоит из двух подзадач, которые отличаются друг от друга ограничениями на входные данные. За решение каждой подзадачи вы получите определенное количество баллов. Описание подзадач следует ниже.

  • В подзадаче E1 (9 баллов) выполняется 2 ≤ n ≤ 400, 2 ≤ k ≤ min(n, 50).
  • В подзадаче E2 (12 баллов) выполняется 2 ≤ n ≤ 30000, 2 ≤ k ≤ min(n, 200).
Выходные данные

Выведите единственное число — максимальное возможное значения выражения.

Примеры
Входные данные
5 3
5 2 4 3 1
Выходные данные
12
Входные данные
4 2
7 4 3 7
Выходные данные
8
Примечание

Рассмотрим первый пример. В оптимальном решении первый подотрезок содержит только первый элемент массива, второй подотрезок состоит из следующих трех, а третий подотрезок содержит только последний элемент массива. Суммы этих подотрезков равны 5, 9 и 1.

Рассмотрим второй пример. Оптимальное решение — взять первые два элемента массива в первый подотрезок, а третий элемент во второй подотрезок. Заметим, что последний элемент массива не входит ни в один подотрезок в этом решении.