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