Дана последовательность из
N натуральных чисел. Известно, что сумма всех чисел последовательности не превышает 10
9. Рассматриваются все её непрерывные подпоследовательности, в которых количество чётных чисел кратно
K = 8. Найдите наибольшую сумму такой подпоследовательности.
Входные данные
Даны два входных файла (
файл A и
файл B), каждый из которых содержит в первой строке количество чисел
N (1 <= N <= 1 000 000). Каждая из следующих
N строк содержит одно натуральное число, не превышающее 1 000.
Пример организации исходных данных во входном файле (для
К=4):
6
9
16
4
12
10
18
В этом наборе можно выбрать последовательности
9+16+4+12+10 (сумма
51) и
4+12+10+18 (сумма
44).
Ответ (для
K = 4):
51.
Предупреждение: для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.