Подарки
(Время: 2 сек. Память: 64 Мб Сложность: 78%)
Дед Мороз предлагает Вове выбрать подарки на Новый год.
Перед мальчиком лежат n подарков в ряд. Каждый подарок характеризуется целым числом, у i-го подарка оно равно ai – количество удовольствия, которое подарок принесёт Вове. Удовольствие может быть как положительным, так и отрицательным, а также равным нулю.
Дед Мороз предложил Вове выбрать два числа l и r таких, что 1 ≤ l ≤ r ≤ n, и взять все подарки с номерами от l до r. Однако k подарков с максимальными характеристиками среди выбранных Вова должен отдать своей младшей сестре Маше. Остальные подарки Вова забирает себе.
Вова хочет выбрать числа l и r так, чтобы суммарное удовольствие от подарков, доставшихся именно ему, было максимальным. Общее удовольствие от набора подарков – это сумма значений ai для подарков в наборе.
Помогите Вове выбрать числа l и r так, что 1 ≤ l ≤ r ≤ n, r − l + 1 ≥ k и общее удовольствие от выбранных подарков без учёта подарков, доставшихся Маше, максимально.
Входные данные
В первой строке входного файла INPUT.TXT записаны два целых числа n и k (1 ≤ n ≤ 200 000, 0 ≤ k ≤ min(100, n)) – количество подарков перед Вовой и количество подарков, которые требуется отдать Маше.
Во второй строке заданы n целых чисел через пробел a1, a2, ... , an (−109 ≤ ai ≤ 109) – количество удовольствия, приносимого подарками.
Выходные данные
В выходной файл OUTPUT.TXT выведите единственное число – общее удовольствие от выбранных Вовой подарков без учёта тех, что достались Маше.
Примеры
№ | INPUT.TXT | OUTPUT.TXT |
1 | 5 0 2 -4 5 -1 7 | 11 |
2 | 5 1 2 -4 5 -1 7 | 4 |
3 | 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.
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
|