CF1764E Doremy's Number Line

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 $ .

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 $ .

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).

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.