8. Подарки
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дед Мороз предлагает Вове выбрать подарки на Новый год.

Перед мальчиком лежат $$$n$$$ подарков в ряд. Каждый подарок характеризуется целым числом, у $$$i$$$-го подарка оно равно $$$a_i$$$ — количество удовольствия, которое подарок принесёт Вове. Удовольствие может быть как положительным, так и отрицательным, а также равным нулю.

Дед Мороз предложил Вове выбрать два числа $$$l$$$ и $$$r$$$ таких, что $$$1 \le l \le r \le n$$$, и взять все подарки с номерами от $$$l$$$ до $$$r$$$. Однако $$$k$$$ подарков с максимальными характеристиками среди выбранных Вова должен отдать своей младшей сестре Маше. Остальные подарки Вова забирает себе.

Вова хочет выбрать числа $$$l$$$ и $$$r$$$ так, чтобы суммарное удовольствие от подарков, доставшихся именно ему, было максимальным. Общее удовольствие от набора подарков — это сумма значений $$$a_i$$$ для подарков в наборе.

Помогите Вове выбрать числа $$$l$$$ и $$$r$$$ так, что $$$1 \le l \le r \le n$$$, $$$r - l + 1 \ge k$$$ и общее удовольствие от выбранных подарков без учёта подарков, доставшихся Маше, максимально.

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

В первой строке записаны два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le n \le 200\,000$$$, $$$0 \le k \le \min(100, n)$$$) — количество подарков перед Вовой и количество подарков, которые требуется отдать Маше.

Во второй строке заданы $$$n$$$ целых чисел через пробел $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$) — количество удовольствия, приносимого подарками.

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

Выведите единственное число — общее удовольствие от выбранных Вовой подарков без учёта тех, что достались Маше.

Система оценки

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

ПодзадачаБаллыОграничения Необходимые подзадачи Информация о проверке
17$$$n \le 200$$$первая ошибка
28$$$n \le 1000$$$1первая ошибка
310$$$n \le 6000$$$1, 2первая ошибка
48$$$k = 0$$$первая ошибка
514$$$k = 1$$$первая ошибка
639$$$n \le 80\,000$$$1–3первая ошибка
7141–6первая ошибка
Примеры
Входные данные
5 0
2 -4 5 -1 7
Выходные данные
11
Входные данные
5 1
2 -4 5 -1 7
Выходные данные
4
Входные данные
5 2
2 -4 5 -1 7
Выходные данные
0
Примечание

В первом примере Вова ничего не должен отдавать Маше, поэтому он выберет $$$l = 3$$$, $$$r = 5$$$, и общее удовольствие от выбранных подарков будет равняться $$$5 + (-1) + 7 = 11$$$.

Во втором примере Вова должен будет отдать Маше подарок с самым большим количеством удовольствия. Тогда он так же выберет $$$l = 3$$$, $$$r = 5$$$, однако общее удовольствие будет равняться $$$5 + (-1) = 4$$$.

В третьем примере Вова должен отдать два подарка с наибольшими характеристиками. В таком случае одним из оптимальных вариантов будет выбрать $$$l = 1$$$, $$$r = 2$$$.