Кассир Вася недавно устроился на работу в одну известную сеть продуктовых магазинов. Его рабочий день длится \(L\) минут. За непродолжительное время работы Вася уже выявил \(n\) постоянных клиентов, \(i\)-й из которых обычно приходит спустя \(t_{i}\) минут после начала рабочего дня, а его обслуживание длится \(l_{i}\) минут. Гарантируется, что к приходу очередного клиента Вася успевает обслужить всех пришедших ранее.
Вася не очень трудолюбивый, поэтому он любит делать перекуры, длительность одного перекура — \(a\) минут. Перекуры могут идти подряд, однако Вася должен быть на рабочем месте во все отрезки времени, когда он должен обслуживать постоянных клиентов, иначе кто-нибудь из них может пожаловаться его боссу. А сколько максимум перекуров может сделать Вася в течение рабочего дня?
Выходные данные
Выведите одно целое число — максимальное количество перекуров.
Примечание
В первом примере Вася может сделать \(3\) перекура: спустя \(2\), \(5\) и \(8\) минут после начала дня.
Во втором примере Вася может сделать \(2\) перекура: спустя \(0\) и \(2\) минуты после начала дня.
В третьем примере Вася не может сделать ни одного перекура.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 11 3
0 1
1 1
|
3
|
|
2
|
0 5 2
|
2
|
|
3
|
1 3 2
1 2
|
0
|