Сложность: 63%
Дед Мороз предлагает Вове выбрать подарки на Новый год.
Перед мальчиком лежат подарков в ряд. Каждый подарок характеризуется целым числом, у -го подарка оно равно – количество удовольствия, которое подарок принесёт Вове. Удовольствие может быть как положительным, так и отрицательным, а также равным нулю.
Дед Мороз предложил Вове выбрать два числа и таких, что , и взять все подарки с номерами от до . Однако подарков с максимальными характеристиками среди выбранных Вова должен отдать своей младшей сестре Маше. Остальные подарки Вова забирает себе.
Вова хочет выбрать числа и так, чтобы суммарное удовольствие от подарков, доставшихся именно ему, было максимальным. Общее удовольствие от набора подарков – это сумма значений для подарков в наборе.
Помогите Вове выбрать числа и так, что , и общее удовольствие от выбранных подарков без учёта подарков, доставшихся Маше, максимально.
Входные данные
В первой строке записаны два целых числа и (, ) – количество подарков перед Вовой и количество подарков, которые требуется отдать Маше.
Во второй строке заданы целых чисел через пробел () – количество удовольствия, приносимого подарками.
Выходные данные
Выведите единственное число – общее удовольствие от выбранных Вовой подарков без учёта тех, что достались Маше.
Подзадачи
№ | баллы | необх. подзадачи | ограничения |
0 | 0 | - | Тесты из условия |
1 | 7 | - | |
2 | 8 | 1 | |
3 | 10 | 1, 2 | |
4 | 8 | - | |
5 | 14 | - | |
6 | 39 | 1, 2, 3 | |
7 | 14 | 1, 2, 3, 4, 5, 6 | Нет дополнительных ограничений |
STDIN | STDOUT |
5 0 2 -4 5 -1 7 | 11 |
5 1 2 -4 5 -1 7 | 4 |
5 2 2 -4 5 -1 7 | 0 |
Примечание
В первом примере Вова ничего не должен отдавать Маше, поэтому он выберет , , и общее удовольствие от выбранных подарков будет равняться .
Во втором примере Вова должен будет отдать Маше подарок с самым большим количеством удовольствия. Тогда он так же выберет , , однако общее удовольствие будет равняться .
В третьем примере Вова должен отдать два подарка с наибольшими характеристиками. В таком случае одним из оптимальных вариантов будет выбрать , .