Барби решила построить самый милый дом в Барбилэнде (благо, пока Кены развлекаются на пляже, она имеет серьезную и уважаемую работу, так что средства позволяют).
Затея у нее правда странная, потому что идею она услышала от Странной Барби. Она собирается построить дом из $$$n$$$ комнат, расположенных вплотную в ряд друг за другом, ведь «модный дом — длинный дом». Каждая комната имеет высоту $$$a$$$ и ширину $$$b$$$, если смотреть на них сбоку, чтобы было видно весь ряд. Таким образом, ее дом будет иметь ширину ровно $$$b \cdot n$$$.
При чем у каждой комнаты есть свое ограничение по тому, на какой высоте можно ее расположить. Будет странно, если чердак будет стоять на земле, а ванная комната — витать в воздухе. По мнению Странной Барби, чтобы дом получился милым, $$$i$$$-я комната не может заходить ниже $$$l_i$$$ или выше $$$h_i$$$ над уровнем земли (то есть потолок не может быть выше $$$h_i$$$, а пол — ниже $$$l_i$$$).
Иными словами, если завести координаты, $$$i$$$-я комната может располагаться только внутри прямоугольника, ограниченного точками $$$((i - 1) \cdot a, l_i)$$$ слева-снизу и $$$(i \cdot a, h_i)$$$ справа-сверху.
Также Барби понимает, что из комнат желательно иметь возможность проходить в соседние, не выходя на улицу. Поэтому она хочет отрегулировать все свои комнаты по высоте так, чтобы можно было построить непрерывный коридор, проходящий на одной высоте внутри комнат через как можно большее количество комнат подряд. Более формально, надо расположить прямоугольники комнат так, чтобы на занимаемом им пространстве можно было выбрать полосу высоты $$$1$$$ максимальной возможной длины.
Помогите Барби построить модный дом с самым длинным возможным коридором!
В первой строке даны три целых числа $$$n$$$, $$$a$$$ и $$$b$$$ — количество комнат, а также высота и ширина каждой комнаты ($$$1 \le n \le 10^6$$$; $$$1 \le a, b \le 10^9$$$).
В $$$i$$$-й из следующих $$$n$$$ строк даны два числа $$$l_i$$$ и $$$h_i$$$ — ограничения снизу и сверху на расположение $$$i$$$-й комнаты ($$$0 \le l_i, h_i \le 10^9$$$; $$$l_i + a \le h_i$$$).
Выведите единственное целое число — максимальную длину коридора, который получится построить в милом доме.
3 3 44 86 103 6
8
2 2 21 43 7
4