← 返回题目列表

Codeforces · 1764/E

E. 多雷米的数轴

中文机器翻译题面 查看原题

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]$$$ 是一种可能的选择。