Дана последовательность из
N чисел. Рассматриваются все её непрерывные подпоследовательности, в которых количество отрицательных чисел
не превышает С. Найдите среди них подпоследовательность с максимальной суммой, длины
L.
Входные данные
Даны два входных файла (
файл A и
файл B), каждый из которых содержит в первой строке подается 3 числа: количество чисел
N (1 <= N <= 1 000 000),
L и
C (1 <= L, C <= N <= 10
6). Каждая из следующих
N строк содержит одно число, не превышающее по модулю 1 000.
Пример организации исходных данных во входном файле (для
L = 3 и
С = 3):
5 3 3
1
-1
2
-2
3
В этом наборе можно выбрать несколько последовательностей, но с максимальной суммой равной 3 будет:
2+(-2)+3.
Ответ (для
L = 3 и
С = 3):
3.
В ответе укажите два числа: сначала значение искомой суммы для файла А, затем для файла B.
Предупреждение: для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.