eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Распределение рабочих станций

Распределение рабочих станций

Ліміт часу 1 секунда
Ліміт використання пам'яті 122 MiB

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

Пенелопа очень ленива и ненавидит разблокировать машины для прибывающих исследователей. Она может разблокировать машины удаленно от своего стола, но считает что такая лакейская задача не соответствует ее квалификации. Если она решит проигнорировать руководящие принципы безопасности, то сможет попросить исследователей не блокировать свои рабочие станции после своего ухода, а затем назначить новых исследователей на рабочие станции, которые уже не используются, но которые все еще не заблокированы. Таким образом, ей нужно только разблокировать каждую рабочую станцию для первого использующего ее исследователя, что было бы большим улучшением для Пенелопы.

К сожалению, неиспользуемые рабочие станции автоматически блокируются, если они не используются более чем m минут. После того, как рабочая станция заперла себя, Пенелопа должна разблокировать ее снова, чтобы следующий исследователь ее использовал. Зная точный график прибытия и ухода исследователей, можете ли Вы сказать Пенелопе, сколько разблокировок она может сэкономить, попросив исследователей не блокировать свои рабочие станции, когда они уйдут, и назначить прибывающих исследователей на рабочие станции оптимальным способом? Вы можете предположить, что всегда имеется достаточное количество рабочих станций.

Вхідні дані

Состоит из:

  • строка с двумя числами n (1n300000) - количество исследователей и m (1m10^8) - количество минут неактивности, после которых станция блокирует сама себя;

  • n строк с двумя числами a и s (1a, s10^8) - означающие что исследователь прибывает в a-ую минуту и остается на работе в точности s минут.

Вихідні дані

Вывести максимальное количество разблокировок, от которого Пенелопа сможет себя избавить.

Приклад

Вхідні дані #1
3 5
1 5
6 3
14 6
Вихідні дані #1
2
Вхідні дані #2
5 10
2 6
1 2
17 7
3 9
15 6
Вихідні дані #2
3
Джерело 2015 ACM North Western European Regional Contest (NWERC), Ноябрь 30, Задача A