Олимпиадный тренинг

Задача .


Задача

Темы:
У медицинской компании есть N пунктов приёма биоматериалов на анализ. Все пункты расположены вдоль автомагистрали и имеют номера, соответствующие расстоянию от нулевой отметки до конкретного пункта. Известно количество пробирок, которое ежедневно принимают в каждом из пунктов. Пробирки перевозят в специальных транспортировочных контейнерах вместимостью V пробирок. Каждый транспортировочный контейнер упаковывается в пункте приёма и вскрывается только в лаборатории. Компания планирует открыть лабораторию в одном из пунктов. Стоимость перевозки биоматериалов равна произведению расстояния от пункта до лаборатории на количество контейнеров с пробирками. Общая стоимость перевозки за день равна сумме стоимостей перевозок из каждого пункта в лабораторию. Лабораторию расположили в одном из пунктов приёма биоматериалов таким образом, что общая стоимость доставки биоматериалов из всех пунктов минимальна. Определите минимальную общую стоимость доставки биоматериалов из всех пунктов приёма в лабораторию.
Входные данные. Даны два входных файла (файл A и файл B), содержит в первой строке число N (2 ≤ N ≤ 5 000 000) – количество пунктов приёма биоматериалов, и число V (1 ≤ V ≤ 1000) – вместимость транспортировочного контейнера. Каждая из следующих N строк содержит два натуральных числа: номер пункта и количество пробирок (не превышающее 10000). Пункты перечислены в произвольном порядке.
Пример входного файла:
6 96
5 4
7 3
1 100
10 190
2 200 
8 2
При таких исходных данных (вместимость транспортировочного контейнера равна 96 пробирок) компании выгодно открыть лабораторию в пункте 2. В том случае сумма транспортных затрат составит 1•2 + 3•1 + 5•1 + 6•1 + 8•2 = 32. Ответ: 32.
В ответе укажите два числа: сначала искомое значение для файла А, затем для файла B.

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
Комментарий учителя