Дана последовательность из
N чисел. Рассматриваются все её непрерывные подпоследовательности, которые содержат ровно
K отрицательных чисел, заканчивающихся цифрой
m. Найдите среди них подпоследовательность с максимальной суммой. Программа должна вывести одно число – максимальную сумму элементов такой подпоследовательности. Гарантируется, что в исходной последовательности существует хотя бы
K отрицательных чисел, заканчивающихся цифрой
m.
Входные данные
В первой строке программа получается три числа: количество чисел в последовательности
N (100 <= N <= 5000000), натуральное число
K и целое число
m (0 <= m <= 9). В каждой из следующих
N строк записано одно целое число, не превышающее по модулю
10000. Гарантируется, что сумма любой подпоследовательности исходной последовательности не превышает по модулю 10
9.
Выходные данные
Выведите на экран ответ на задачу.
Примеры
| № |
Входные данные |
Выходные данные |
Пояснение |
| 1 |
8 2 3
6
-3
-2
4
-1
-13
8
13 |
12 |
Нужные нам числа -3 и -13. Вся исходная последовательность даст максимальную сумму элементов. |