HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Sections > Unsorted > problem:


Разрядка и трансляции

Guest
• Discussion of problem (8)

Section problems

• Прямоугольники
• Прямоугольники
• Прямоугольники
• Путёвка и считалка
• Радиовышки
• Разворот
• Разложение на простые множители
• Разложение на слагаемые
• Разрядка и трансляции
• Распределение студентов
• Распродажа
• 1
• Расстояния — 1
• Расстояния — 2
• Расстояния — 3
• Роботы
• Ромб

Feedback

If you notice incorrect translations in Contester, please let author know.

Time limit 10000/10000/10000/10000 ms. Memory limit 65536/65536/65536/65536 Kb.

Разрядка и трансляции
Разрядка и трансляции
ограничение по времени на тест
10 секунд
ограничение по памяти на тест
64 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Сегодня большой день для любителей онлайн-игр — всё мировое сообщество следит за финальными матчами чемпионата по знаменитой многопользовательской игре. У Макса, разумеется, всё не как у людей — в этот знаменательный день он умудрился оказаться в поезде, да ещё и с почти разряженным ноутбуком!

Разумеется, Макс заранее знал о чемпионате и составил список из N матчей, которые он хотел бы посмотреть. Матчи чемпионата транслируются в Интернете: i-й матч начинается в момент времени Li и заканчивается в момент времени Ri. Несколько матчей могут транслироваться одновременно.

К сожалению, ноутбук Макса вот-вот разрядится: заряда аккумулятора хватит на непрерывную работу в течение M единиц времени. Макс пока выключил свой ноутбук: он решил, что включит его в определённый момент времени и будет смотреть матчи, не отключая ноутбук, до тех пор, пока он не разрядится.

Подскажите Максу, когда именно включить ноутбук, чтобы он сумел посмотреть как можно больше матчей целиком. При необходимости Макс может смотреть несколько трансляций одновременно — на скорость разрядки ноутбука это не влияет.

Входные данные

Первая строка содержит целое число N (1 ≤ N ≤ 105) — количество матчей, трансляцию которых Макс хотел бы посмотреть.

Следующие N строк описывают матчи. Каждая из них содержит целые числа Li и Ri (1 ≤ Li ≤ Ri ≤ 109) — соответственно момент начала и момент окончания матча.

Следующая строка содержит целое число M (1 ≤ M ≤ 109) — количество единиц времени, в течение которых ноутбук Макса может работать, прежде чем разрядится.

Выходные данные

Выведите одно целое число — максимальное количество матчей, которые Макс сможет посмотреть целиком.

Примеры

Входные данные
4
0 60
80 100
50 75
95 120
80
Выходные данные
3
Входные данные
4
0 60
80 100
50 75
95 120
40
Выходные данные
2

Для отправки решений необходимо выполнить вход.

www.contester.ru