AT_agc072_a [AGC072A] Rhythm Game

Consider the following rhythm‑action game on the real line. > There are $ N $ buttons. The $ i $ ‑th button $ (1 \le i \le N) $ appears at coordinate $ X_i $ exactly $ T_i $ seconds after the game starts. Each button disappears $ D + 0.5 $ seconds after it appears. > > The player starts at coordinate $ 0 $ at time $ 0 $ , and must press all $ N $ buttons to win the game. The buttons may be pressed in any order. However, after pressing a button and before pressing another, the player must visit coordinate $ 0 $ at least once.Violating this rule results in disqualification. Ms. AtCoder can move at speed $ 1 $ on the line. Can she win the game? Pressing a button takes negligible time. Solve $ \mathrm{TESTCASES} $ test cases.

The input is given from Standard Input in the following format, where $ \mathrm{case}_k $ represents the $ k $ -th test case: > $ \mathrm{TESTCASES} $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_{\mathrm{TESTCASES}} $ Each test case is given in the following format: > $ N $ $ D $ $ T_1 $ $ X_1 $ $ T_2 $ $ X_2 $ $ \vdots $ $ T_N $ $ X_N $

Print $ \mathrm{TESTCASES} $ lines. The $ k $ -th line should contain `Yes` if the game is winnable for the $ k $ -th test case, and `No` otherwise.

### Sample Explanation 1 For the first test case, the game can be won as follows, so the first line contains `Yes`. Elapsed timeAction / Event $ 0 $ secondsGame starts. $ 5 $ secondsStart moving right from coordinate $ 0 $ . $ 25 $ secondsArrive at coordinate $ 20 $ and stop. $ 30 $ secondsButton $ 1 $ appears at coordinate $ 20 $ . Press it immediately and head left. $ 50 $ secondsArrive at coordinate $ 0 $ . Head right. Button $ 2 $ appears at coodinate $ 10 $ . $ 60 $ secondsArrive at coordinate $ 10 $ and press button $ 2 $ (before it disappears at $ 60.5 $ seconds).For the second test case, the game is unwinnable, so the second line contains `No`. For the third test case, the game is winnable, so the third line contains `Yes`. For the fourth test case, the game is unwinnable, so the fourth line contains `No`. ### Constraints - $ 1 \le \mathrm{TESTCASES} \le 100\,000 $ - $ 1 \le N \le 5\,000 $ - $ 0 \le D \le 10^{12} $ - $ 0 \le T_1 \le T_2 \le \dots \le T_N \le 10^{12} $ - $ 1 \le X_i \le 10^{12} $ - The sum of $ N $ over all test cases is at most $ 100\,000 $ . - The sum of $ N^2 $ over all test cases is at most $ 2.5 \times 10^7 $ . - All input values are integers.