Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

C. Душ
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Как студент факультета компьютерных наук, Алекс сталкивается с трудной задачей — принятием душа. Он старается принимать душ ежедневно, но, несмотря на все его усилия, всегда возникают препятствия. Ему требуется $$$s$$$ минут, чтобы принять душ, а в сутках всего $$$m$$$ минут!

У него уже запланировано $$$n$$$ задач на день. Задача $$$i$$$ представлена интервалом $$$(l_i$$$, $$$r_i)$$$, что означает, что Алекс занят и не может принять душ в этот временной интервал (в любой момент времени строго между $$$l_i$$$ и $$$r_i$$$). Ни одна из задач не пересекается с другой.

Учитывая все $$$n$$$ временных интервалов, сможет ли Алекс принять душ в этот день? Другими словами, будет ли у Алекса свободный временной интервал длиной не менее $$$s$$$?

В первом примере Алекс может принять душ в первые $$$3$$$ минуты дня и не пропустить ни одну из задач.

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

Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных.

Первая строка каждого набора входных данных содержит три целых числа $$$n$$$, $$$s$$$ и $$$m$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$; $$$1 \leq s, m \leq 10^9$$$) — количество временных интервалов, которые Алекс уже запланировал, время, необходимое Алексу для принятия душа, и количество минут в сутках.

Затем следуют $$$n$$$ строк, $$$i$$$-я из которых содержит два целых числа $$$l_i$$$ и $$$r_i$$$ ($$$0 \leq l_i < r_i \leq m$$$) — временной интервал $$$i$$$-й задачи. Ни одна из задач не накладывается на другую.

Дополнительное ограничение на входные данные: $$$l_i > r_{i-1}$$$ для каждого $$$i > 1$$$.

Сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите «YES» (без кавычек), если Алекс может принять душ для данного набора входных данных, и «NO» (также без кавычек) в противном случае.

Вы можете выводить «YES» и «NO» в любом регистре (например, строки «yEs», «yes», и «Yes» будут признаны положительным ответом).

Пример
Входные данные
4
3 3 10
3 5
6 8
9 10
3 3 10
1 2
3 5
6 7
3 3 10
1 2
3 5
6 8
3 4 10
1 2
6 7
8 9
Выходные данные
YES
YES
NO
YES