Эффективное программирование
У инкассаторской службы есть N пунктов приёма купюр для перевозки в главный офис. Все пункты расположены вдоль автомагистрали и имеют номера, соответствующие расстоянию от нулевой отметки до конкретного пункта. Известно количество купюр, которое ежедневно принимают в каждом из пунктов. Купюры перевозят в специальных кейсах вместимостью V купюр на расстояние не более M. Каждый такой кейс упаковывается в пункте приёма и вскрывается только в офисе. Инкассаторской служба планирует открыть офис в одном из пунктов. Офис расположили в одном из пунктов приёма купюр таким образом, чтобы перевезти как можно больше купюр (ведь ездить можно на расстояние не более M от текущей точки). Найдите количество кейсов, которые понадобятся для перевозки максимально возможного количества купюр.
Входные данные. Даны два входных файла (Файл А и Файл В), содержит в первой строке число N (2 ≤ N ≤ 5 000 000) – количество пунктов приёма купюр, и число V (1 ≤ V ≤ 1000) – вместимость транспортировочного кейса, и число M (1 ≤ M ≤ 100000) - расстояние, на которое можно ездить от текущей Ni точки (0 ≤ i < N) . Каждая из следующих N строк содержит два натуральных числа: номер пункта и количество купюр (не превышающее 10000). Пункты перечислены в произвольном порядке.
Пример входного файла:
6 96 3
5 4
7 3
1 100
10 190
2 200
8 2
При таких исходных данных (вместимость транспортировочного кейса равна 96 купюр) службе выгодно открыть офис в пункте 2. В том случае будет перевезено максимальное количество купюр, а кейсов на их перевозку будет потрачено = 200 / 96 + 100 / 96 + 4 / 96 = 3 + 2 + 1 = 6. Ответ: 6.
В ответе укажите два числа: сначала искомое значение для файла А, затем для файла B.