a27_0055

Геодезист измеряет высоту над уровнем моря (в миллиметрах) относительно уровня начала дороги, для каждой из N её метровых отметок. Нумерация отметок начинается с единицы.

Проектировщикам необходимо выбрать участок дороги длиной не менее К метров, на котором значение суммы всех высот, выраженное в миллиметрах, максимально. Это значение называется оценкой участка дороги. Начало и конец искомого участка совпадают с метровыми отметками на дороге. Началом участка считается метровая отметка дороги с меньшим номером.

Определите две метровые отметки дороги так, чтобы расстояние между ними было не менее К метров, а оценка соответствующего участка дороги — максимально возможной. Укажите в ответе найденное числовое значение максимальной оценки, выраженное в миллиметрах.

Входные данные

Даны два входных файла (файл А и файл В), каждый из которых в первой строке содержит натуральное число К — минимально допустимое расстояние (в метрах) между двумя отметками дороги, а во второй — количество метровых отметок дороги
N (1⩽ N ⩽ 10 000 000, N > К).

В каждой из следующих N строк находится одно целое число, не превышающее по модулю 10 000 000: высота относительно уровня
начального участка дороги (в миллиметрах) на соответствующей метровой отметке дороги.

В ответе укажите два числа: сначала значение искомой величины для файла А, затем — для файла В.

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

• a27_0055A.txt
• a27_0055B.txt