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