По каналу связи ежедневно раз в день в течение \(N\) дней (\(N\) — натуральное число) передаётся последовательность натуральных чисел — сумма выручки в некотором отделении банка за день.

Определите три таких переданных числа, чтобы между моментами передачи любых из двух из них прошло не менее \(K\) дней, а сумма этих трёх чисел была минимально возможной. Запишите в ответе найденную сумму.

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

Даны два входных файла (файл \(A\) и файл \(B\)), каждый из которых в первой строке содержит натуральное число \(K\) — минимальное количество дней, которое должно пройти между моментами передачи сумм выручки, а во второй — количество переданных значений \(N\) ( \(1 \leqslant N \leqslant 10~000~000\), \(N>K\)). В каждой из следующих \(N\) строк находится одно натуральное число, не превышающее \(10~000~000\), которое обозначает сумму выручки в отделении банка за соответствующий день.

Запишите в ответе два числа: сначала значение искомой величины для файла \(A\), затем — для файла \(B\).

Типовой пример организации данных во входном файле
\(2\)
\(6\)
\(15\)
\(26\)
\(30\)
\(23\)
\(22\)
\(20\)
При таких исходных данных искомая величина равна \(65\) — это сумма значений выручки, полученной в первый, третий и шестой дни.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.

Предупреждение: для обработки файла \(B\) не следует использовать переборный алгоритм, вычисляющий сумму для всех всевозможных вариантов, поскольку по такому алгоритму программа будет выполняться слишком долго.

Файл с данными

У медицинской компании есть \(N\) пунктов приёма биоматериалов на анализ. Все пункты расположены вдоль автомагистрали и имеют номера, соответствующие расстоянию от нулевой отметки до конкретного пункта. Известно количество пробирок, которое ежедневно принимают в каждом из пунктов. Пробирки перевозят в специальных транспортировочных контейнерах вместимостью не более \(36\) штук. Каждый транспортировочный контейнер упаковывается в пункте приёма и вскрывается только в лаборатории. Компания планирует открыть лабораторию в одном из пунктов. Стоимость перевозки биоматериалов равна произведению расстояния от пункта до лаборатории на количество контейнеров с пробирками. Общая стоимость перевозки за день равна сумме стоимостей перевозок из каждого пункта в лабораторию. Лабораторию расположили в одном из пунктов приёма биоматериалов таким образом, что общая стоимость доставки биоматериалов из всех пунктов минимальна.

Определите минимальную общую стоимость доставки биоматериалов из всех пунктов приёма в лабораторию.

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

Дано два входных файла (файл \(A\) и файл \(B\)), каждый из которых в первой строке содержит число \(N\) (\(1 \leq N \leq 10~000~000\)) – количество пунктов приёма биоматериалов. В каждой из следующих \(N\) строк находится два числа: номер пункта и количество пробирок в этом пункте (все числа натуральные, количество пробирок в каждом пункте не превышает \(1~000\)). Пункты перечислены в порядке их расположения вдоль дороги, начиная от нулевой отметки. В ответе укажите два числа: сначала значение искомой величины для файла \(A\), затем – для файла \(B\).

Типовой пример организации данных во входном файле

\(6\)
\(1\)    \(100\)
\(2\)    \(200\)
\(5\)    \(4\)
\(7\)    \(3\)
\(8\)    \(2\)
\(10\)    \(190\)

При таких исходных данных и вместимости транспортировочного контейнера, составляющей \(96\) пробирок, компании выгодно открыть лабораторию в пункте \(2\). В этом случае сумма транспортных затрат составит: \(1 \cdot 2 + 3 \cdot 1 + 5 \cdot 1 + 6 \cdot 1 + 8 \cdot 2 = 32\).

Файл с данными