EduBrick
← вернуться к уроку · Практика: Жадные идеи и их ловушки

Платформы с уборкой

5000 мс · 256 МБ · всё или ничего

На станции nn поездов: поезд прибывает в момент aia_i и отправляется в момент did_i. После отправления платформу убирают ещё cc минут, и всё это время она занята.

То есть платформа свободна для нового поезда только начиная с момента di+c+1d_i + c + 1. Какое наименьшее число платформ нужно станции?

Формат ввода

В первой строке числа nn от 11 до 21052 \cdot 10^5 и cc от 00 до 10910^9. Во второй — 2n2n чисел: пары aa и dd подряд, 1ad1091 \le a \le d \le 10^9.

Формат вывода

Одно число.

Примеры

ввод
3 1
1 5 2 6 7 8
вывод
2

Примечание

Уборка не требует нового алгоритма: достаточно считать, что поезд занимает платформу до момента di+cd_i + c.

Войдите, чтобы отправлять решения.
← Вернуться к уроку