Doremy 的数轴

• 时间限制：2 秒
• 内存限制：512 MiB

题目描述

Doremy 有两个长度为 $n$ 的整数数组 $a,b$，以及一个整数 $k$。

数轴上的所有整数起初都没有颜色。Doremy 先选择一个 $1,2,\ldots,n$ 的排列 $p$，再依次执行 $n$ 次操作。第 $i$ 次操作使用颜色 $p_i$，并选择一个尚未染色的整数 $x$。所选的 $x$ 必须满足下列条件之一：

• $x\le a_{p_i}$；
• 存在一个已经染色的整数 $y$，满足 $y\le a_{p_i}$ 且 $x\le y+b_{p_i}$。

随后，整数 $x$ 被染成颜色 $p_i$。

请判断是否存在一种排列和每次所选的整数，使整数 $k$ 最终被染成颜色 $1$。

输入格式

第一行一个整数 $t$，表示测试数据组数。

每组测试数据第一行包含两个整数 $n,k$。

随后 $n$ 行，第 $i$ 行包含两个整数 $a_i,b_i$。

输出格式

对每组测试数据输出一行。如果可以使整数 $k$ 被染成颜色 $1$，输出 YES；否则输出 NO。

样例输入

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

数据范围

对所有测试数据：

• $1\le t\le 10^4$；
• $1\le n\le 10^5$；
• $1\le k\le 10^9$；
• $1\le a_i,b_i\le 10^9$；
• 所有测试数据中 $n$ 的总和不超过 $10^5$。

说明

在样例的第二组数据中，可以先用颜色 $2$ 给整数 $8$ 染色，再用颜色 $1$ 给整数 $16$ 染色。

题目来源：Codeforces 1764E。