z27-45784_AB
Задача
Задание выполняется с использованием прилагаемых файлов.
На кольцевой автодороге с двусторонним движением находится N домов.
Длина кольцевой автодороги равна K км, нулевой километр и K-й километр находятся в одной точке.
Ежедневно по домам требуется разносить письма. Письма раскладываются по сумкам, вместимость которых равна 20 единиц. За один рейс автомобиль доставляет почту только в один дом. Нельзя довозить более одной неполной сумки. Стоимость доставки в каждый дом равна произведению количество сумок на расстояние от дома до почтамта. Почтамт расположен на таком километре автодороги, что суммарная стоимость доставки минимальна, а сам почтамт удалён от ближайших домов не менее чем на M километров.
Определите минимальную километровую отметку, где можно расположить почтамт.
В ответ укажите суммарную стоимость доставки из почтамта, расположенного на этом километре.
Входные данные:
Даны два входных файла: файл A (27-45784A.txt) и файл B (27-45784B.txt), каждый из которых в первой строке содержит три числа:
N (1 ≤ N ≤ 200 000) – количество домов; K (1 ≤ K ≤ 1 000 000) – длина кольцевой автодороги, и M (1 ≤ M ≤ 300) – расстояние, на котором разрешено устанавливать почтамт. В каждой из следующих N строк находятся два числа: километровая отметка, где расположен дом, и количество писем, которое требуется туда доставить (километровые отметки отсортированы по возрастанию).
Пример входного файла:
7 20 2
1 100
3 134
5 24
8 57
12 89
15 35
20 435
Для приведённых данных находим количество сумок, которые нужно доставить в дома: 5, 7, 2, 3, 5, 2, 22. Ответом могут являться следующие километровые отметки, которые удовлетворяют условию задачи: 10, 17, 18. Суммарная стоимость доставки будет минимальной, если расположить почтамт на 18-м километре, она равна 3·5 + 5·6 + 7·2 + 10·3 + 6·5 + 3·2 + 2·22 = 174. Ответ: 174.
В ответе укажите два числа:
- в 1-й строке искомое значение для файла А,
- в 2 -й строке искомое значение для файла B.
Выберите правильный ответ, либо введите его в поле ввода
Комментарий учителя