|
По каналу связи передаётся последовательность целых неотрицательных чисел – показания прибора, полученные
с интервалом в 1 мин. в течение
T
мин. (
T
– целое число). Прибор измеряет количество атмосферных осадков, полученное регистратором за минуту, предшествующую моменту регистрации,
и передаёт это значение в условных единицах измерения.
Определите два таких переданных числа, чтобы между моментами их передачи прошло
не менее
K
мин., а их сумма была максимально возможной. Укажите найденное суммарное количество осадков.
Входные данные
Даны два входных файла (файл
A
и файл
B
), каждый из которых
в первой строке содержит натуральное число
K
–
количество минут, которое должно пройти между двумя передачами показаний, а во второй – количество переданных показаний
N
(1 ≤
N
≤ 10 000 000,
N
>
K
). В каждой из следующих
N
строк находится одно целое неотрицательное число, не превышающее 100 000, обозначающее количество осадков за соответствующую минуту.
Запишите в ответе два числа: сначала значение искомой величины для файла
А
, затем – для файла
B
.
Типовой пример организации данных во входном файле
3
5
15
10
200
0
30
При таких исходных данных максимально возможное суммарное количество осадков равно 45 – это сумма осадков, выпавших на первой и пятой минутах.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
Предупреждение:
для обработки файла
B
не следует
использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.
|