J. Твоя игра
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Поликарп вышел в финал телепередачи «Твоя игра».

В финале для Поликарпа подготовлены $$$n$$$ вопросов, пронумерованных целыми числами от $$$1$$$ до $$$n$$$, причем каждый вопрос имеет свою стоимость. Если Поликарп ответит на вопрос, то к его счету прибавится стоимость вопроса, а если Поликарп не ответит на вопрос, то из его счета вычтется стоимость вопроса. Изначально счет Поликарпа равен нулю.

По правилам финала сначала Поликарп должен удалить ровно $$$k$$$ вопросов, которые ему точно не будут заданы. Относительный порядок остальных вопросов останется без изменений.

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

Поликарп перед началом финала узнал темы всех $$$n$$$ вопросов. Теперь он точно знает на какие вопросы он сможет ответить верно, а на какие не сможет.

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

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

В первой строке следуют два целых числа $$$n$$$ и $$$k$$$ ($$$2 \le n \le 200\,000$$$, $$$1 \le k \le min(10, n - 1)$$$) — изначальное количество вопросов и количество вопросов, которые Поликарп должен удалить в начале финала.

Во второй строке следует последовательность целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$-10^{9} \le a_i \le 10^{9}$$$, $$$a_i \neq 0$$$), где $$$|a_i|$$$ равно стоимости $$$i$$$-го вопроса. Если $$$a_i \gt 0$$$, то Поликарп сможет ответить на $$$i$$$-й вопрос. Если $$$a_i \lt 0$$$, то Поликарп не сможет ответить на $$$i$$$-й вопрос.

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

Выведите максимальный счет, который может набрать Поликарп в конце финала. Обратите внимание, что ответ может быть отрицательным числом.

Примеры
Входные данные
5 1
1 2 -4 3 2
Выходные данные
8
Входные данные
10 2
4 3 -4 -2 -2 -2 3 -2 3 6
Выходные данные
17
Входные данные
13 4
-3 -2 -3 -3 -2 -4 -3 -2 -3 -3 -4 -3 -2
Выходные данные
-9
Примечание

В первом примере Поликарпу нужно удалить третий вопрос. Затем ему будут заданы четыре вопроса $$$[1, 2, 3, 2]$$$. Поликарпу не нужно пропускать ни одного вопроса, потому что он сможет ответить на все. Таким образом, его счет в конце финала будет равен $$$1 + 2 + 3 + 2 = 8$$$.

Во втором примере Поликарп может, например, удалить третий и пятый вопросы. Затем ему будут заданы восемь вопросов $$$[4, 3, -2, -2, 3, -2, 3, 6]$$$. Из них Поликарп может, например, пропустить третий и шестой вопросы. Таким образом, его счет в конце финала будет равен $$$4 + 3 + (-2) + 3 + 3 + 6 = 17$$$.