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

У Дореми есть два массива целых чисел $$$a$$$ и $$$b$$$ из $$$n$$$ целых чисел каждый, а также целое число $$$k$$$.

Изначально у нее есть числовая прямая, где никакие точки не покрашены. Она выбирает перестановку $$$p$$$ чисел $$$[1,2,\ldots,n]$$$, затем делает $$$n$$$ ходов. На $$$i$$$-м ходу Дореми делает следующее:

  • Она выбирает непокрашенное целое число $$$x$$$ на числовой прямой, удовлетворяющее
    • $$$x \leq a_{p_i}$$$, или
    • существует покрашенное целое число $$$y$$$ такое, что $$$y \leq a_{p_i}$$$ и $$$x \leq y+b_{p_i}$$$.
  • Она красит $$$x$$$ в цвет $$$p_i$$$.

Определите, может ли целое число $$$k$$$ оказаться покрашенным в цвет $$$1$$$.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1\le t\le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le n \le 10^5$$$, $$$1 \le k \le 10^9$$$).

Каждая из следующих $$$n$$$ строк содержит два целых числа $$$a_i$$$ и $$$b_i$$$ ($$$1 \le a_i,b_i \le 10^9$$$).

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

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

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

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

Пример
Входные данные
6
4 16
5 3
8 12
10 7
15 1
4 16
8 12
10 7
15 1
5 3
4 16
10 7
15 1
5 3
8 12
4 16
15 1
5 3
8 12
10 7
1 1000000000
500000000 500000000
2 1000000000
1 999999999
1 1
Выходные данные
NO
YES
YES
YES
NO
YES
Примечание

В первом примере невозможно покрасить число $$$16$$$ в цвет $$$1$$$.

Во втором примере $$$p=[2,1,3,4]$$$ — одно из возможных решений, ниже показаны подробности.

  • На первом ходу выбирается $$$x=8$$$ и окрашивается в цвет $$$2$$$, так как $$$x=8$$$ еще не покрашено, и $$$x \le a_2$$$.
  • На втором ходу выбирается $$$x=16$$$ и окрашивается в цвет $$$1$$$, так как существует покрашенная точка $$$y=8$$$ такая, что $$$y\le a_1$$$ и $$$x \le y + b_1$$$.
  • На третьем ходу выбирается $$$x=0$$$ и окрашивается в цвет $$$3$$$, так как $$$x=0$$$ еще не покрашено, и $$$x \le a_3$$$.
  • На четвертом ходу выбирается $$$x=-2$$$ и окрашивается в цвет $$$4$$$, так как $$$x=-2$$$ еще не покрашено, и $$$x \le a_4$$$.
  • В итоге числа $$$-2,0,8,16$$$ покрашены в цвета $$$4,3,2,1$$$ соответственно.

В третьем примере одно из возможных решений — $$$p=[2,1,4,3]$$$.

В четвертом примере одно из возможных решений — $$$p=[2,3,4,1]$$$.