Задача № 108
По каналу связи передаётся последовательность целых чисел - показания прибора. В течение \( N \) мин. (\( N \) - натуральное число) прибор ежеминутно регистрирует значение напряжения (в условных единицах) в электрической сети и передаёт его на сервер.
Определите три таких переданных числа, чтобы между моментами передачи любых двух из них прошло не менее \( K \) мин., а сумма этих трёх чисел была максимально возможной. Запишите в ответе найденную сумму.
Входные данные
Даны два входных файла (файл \( A \) и файл \( B \)), каждый из которых в первой строке содержит натуральное число \( K \) - минимальное количество минут, которое должно пройти между моментами передачи показаний, а во второй строке - количество переданных показаний \( N \) \( (1 \leqslant N \leqslant 10 000 000, N > K) \). В каждой из следующих \( N \) строк находится одно целое число, по модулю не превышающее 10 000 000, которое обозначает значение напряжения в соответствующую минуту.
Запишите в ответе два числа: сначала значение искомой величины для файла \( A \), затем - для файла \( B \).
Типовой пример организации данных во входном файле
2
150
-150
20
-200
-300
При таких исходных данных искомая величина равна 170 - это сумма значений, зафиксированных на первой, третьей и шестой минутах измерений.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
Предупреждение: для обработки файла В не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.
