a27_0037

По каналу связи передаётся последовательность целых неотрицательных чисел – показания прибора, полученные с интервалом в 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 не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.

Файлы к заданию:

• a27_0037A.txt
• a27_0037B.txt