Doremy's Number Line
Contest: Codeforces Global Round 24
Difficulty rating: 2400
Tags: dp, greedy, sortings

Doremy has two arrays $$$a$$$ and $$$b$$$ of $$$n$$$ integers each, and an integer $$$k$$$.

Initially, she has a number line where no integers are colored. She chooses a permutation $$$p$$$ of $$$[1,2,\ldots,n]$$$ then performs $$$n$$$ moves. On the $$$i$$$-th move she does the following:

- Pick an uncolored integer $$$x$$$ on the number line such that either:   $$$x \leq a_{p_i}$$$; or  there exists a colored integer $$$y$$$ such that $$$y \leq a_{p_i}$$$ and $$$x \leq y+b_{p_i}$$$.
- Color integer $$$x$$$ with color $$$p_i$$$.

Determine if the integer $$$k$$$ can be colored with color $$$1$$$.

Input format:
The input consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1\le t\le 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 10^5$$$, $$$1 \le k \le 10^9$$$).

Each of the following $$$n$$$ lines contains two integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \le a_i,b_i \le 10^9$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output format:
For each test case, output "YES" (without quotes) if the point $$$k$$$ can be colored with color $$$1$$$. Otherwise, output "NO" (without quotes).

You can output "YES" and "NO" in any case (for example, strings "yEs", "yes" and "Yes" will be recognized as a positive response).

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
For the first test case, it is impossible to color point $$$16$$$ with color $$$1$$$.

For the second test case, $$$p=[2,1,3,4]$$$ is one possible choice, the detail is shown below.

- On the first move, pick $$$x=8$$$ and color it with color $$$2$$$ since $$$x=8$$$ is uncolored and $$$x \le a_2$$$.
- On the second move, pick $$$x=16$$$ and color it with color $$$1$$$ since there exists a colored point $$$y=8$$$ such that $$$y\le a_1$$$ and $$$x \le y + b_1$$$.
- On the third move, pick $$$x=0$$$ and color it with color $$$3$$$ since $$$x=0$$$ is uncolored and $$$x \le a_3$$$.
- On the forth move, pick $$$x=-2$$$ and color it with color $$$4$$$ since $$$x=-2$$$ is uncolored and $$$x \le a_4$$$.
- In the end, point $$$-2,0,8,16$$$ are colored with color $$$4,3,2,1$$$, respectively.

For the third test case, $$$p=[2,1,4,3]$$$ is one possible choice.

For the fourth test case, $$$p=[2,3,4,1]$$$ is one possible choice.

Example input:
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

Example output:
NO
YES
YES
YES
NO
YES

Editorial:
First if $$$k$$$ can be colored with certain color, then any $$$K<k$$$ can also be colored the this color. So we only need to calculate what is the biggest number color $$$1$$$ can be. Apparently this value will not exceed $$$x_1+y_1$$$.
If $$$x_1$$$ is not maximum among all $$$x$$$, you can pick any $$$j$$$ such that $$$x_j\ge x_1$$$. Color point $$$x_1$$$ with color $$$j$$$, then color point $$$x_1+y_1$$$ with color $$$1$$$. So $$$x_1+y_1$$$ is the answer in this case.
If $$$x_1$$$ is maximum, just enumerate which color precedes color $$$1$$$.
• No color precedes. Directly color $$$x_1$$$ with color $$$1$$$.
• Color $$$j$$$ precedes, but $$$x_j$$$ is not maximum among $$$x_2,x_3,\cdots,x_n$$$. In this case, point $$$x_j+y_j$$$ can always be colored with color $$$j$$$. Point $$$\min\{x_j+y_j,x_1\}+y_1$$$ can be colored with color $$$1$$$.
• Color $$$j$$$ precedes, meanwhile $$$x_j$$$ is maximum among $$$x_2,x_3,\cdots,x_n$$$. In this case, we can just enumerate which color precedes color $$$j$$$, which leads to a recursion, until there is only one color remaining.
Time complexity is $$$O(n \log n)$$$ due to sorting.