Doremy 有两个数组 $$$a$$$ 和 $$$b$$$,每个数组都有 $$$n$$$ 个整数,以及一个整数 $$$k$$$。
最初,她有一条没有对整数着色的数轴。她选择 $$$[1,2,\ldots,n]$$$ 的排列 $$$p$$$,然后执行 $$$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$$$。
输出
对于每个测试用例,如果点 $$$k$$$ 可以用颜色 $$$1$$$ 着色,则输出“YES”(不带引号)。否则,输出“NO”(不带引号)。
在任何情况下都可以输出“YES”和“NO”(例如,字符串“yEs”、“yes”和“Yes”将被识别为肯定响应)。
示例
输入 #1
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
输出 #1
NO YES YES YES NO YES
注意
对于第一个测试用例,不可能用颜色 $$$1$$$ 为点 $$$16$$$ 着色。
对于第二个测试用例,$$$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]$$$ 是一种可能的选择。