На кольцевой автодороге с двусторонним движением находится N заправочных станций. Длина кольцевой автодороги равна K км, нулевой километр и K-й километр находятся в одной точке. Код заправочной станции совпадает с расстоянием этой станции до нулевой отметки дороги в километрах. На заправочные станции нужно ежедневно доставлять бензин из бензохранилища, которое требуется разместить рядом с одной из заправочных станций. Бензин поставляется в цистернах объёмом V м3 каждая, затраты на доставку вычисляются как произведение расстояния на количество поездок бензовоза. За один рейс бензовоз доставляет бензин только на одну заправочную станцию. Бензохранилище расположено так, чтобы суммарные затраты на доставку бензина были минимальными. Определите минимально возможные суммарные затраты на доставку бензина.
Входные данные. Даны два входных файла (
файл A и
файл B), каждый из которых в первой строке содержит три числа N, K и V (1 < N ≤ 10 000 000, 1 < K ≤ 10 000 000, 1 < V ≤ 1000) – количество заправочных станций, длина кольцевой автодороги в километрах и объём цистерны. В каждой из следующих N строк находятся два числа: номер километра кольцевой автодороги, на котором расположена заправочная станция, и количество бензина, которое нужно туда доставить (все числа натуральные). Заправочные станции перечисляются в порядке их расположения на автодороге.
Пример входного файла:
5 11 3
1 8
3 7
5 6
7 5
9 3
При таких исходных данных лучше всего расположить бензохранилище около заправочной станции с кодом 3. При этом затраты на доставку бензина составят 2·3 + 2·2 + 4·2 + 5·1 = 23. Ответ: 23.
В ответе укажите два числа: сначала искомое значение для файла А, затем для файла B.