У транспортной компании есть N пунктов приёма отправлений. Все пункты расположены вдоль улицы и имеют номера, соответствующие расстоянию от нулевой отметки до конкретного пункта. Известно количество отправлений, которое ежедневно принимают в каждом из пунктов.
Компания планирует открыть склад в одном из пунктов приёма, куда необходимо перемещать отправления со всех пунктов приема. Отправления перевозят в автомобилях вместимостью не более M отправлений. Автомобиль за один рейс может привезти отправления на склад только из одного пункта приёма, при этом из одного пункта приема отправлений допустимо делать только один рейс с неполной загрузкой автомобиля. Стоимость рейса считается равной расстоянию от пункта приема до склада. Место для склада выбрали таким образом, чтобы стоимость доставки всех отправлений была минимальной. Определите стоимость перевозки всех отправлений из пунктов приёма.
Входные данные
Даны два входных файла (файл A и файл B), каждый из которых в первой строке содержит два числа N и M (1 ≤ N ≤ 200 000, 1 ≤ M ≤ 200) – количество пунктов приёма отправлений и количество отправлений, которые может перевозить автомобиль за один рейс. В каждой из следующих N строк находятся два числа: номер пункта и количество отправлений, принимаемых на этом пункте за сутки (все числа натуральные, количество отправлений в каждом пункте не превышает 1000). Пункты перечислены в порядке их расположения вдоль улицы, считая от нулевой отметки.
В ответе укажите два числа: сначала значение искомой величины для файла А, затем – для файла B.
Типовой пример организации данных во входном файле
6 20
1 10
3 20
6 10
7 15
8 20
10 35
При таких исходных данных компании выгодно открыть склад в пункте 7. В этом случае стоимость перевозки составит: 6 + 4 + 1 + 1 + 6.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
Предупреждение: для обработки файла B не следует использовать переборный алгоритм, вычисляющий количество рейсов для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.
