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