Дана последовательность из
N чисел. Известно, что сумма всех чисел последовательности не превышает 10
9. Рассматриваются все её непрерывные подпоследовательности, в которых количество положительных чисел кратных двум кратно
K. Найдите такую подпоследовательность с максимальной суммой.
Формат входных данных
В первой строке записаны два натуральных числа
N и
K (
1 <= N <= 1 000 000, 1 <= K <= 100). Каждая из следующих
N строк содержит одно число, не превышающее по модулю 1 000.
Формат выходных данных
Выведите одно число - максимальную сумму подпоследовательности, удовлетворяющей условию задачи. Гарантируется, что как минимум одна такая подпоследовательность существует.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
10 3
49
30
12
24
35
15
11
9
24
26
|
185
|