{"raw_statement":[{"iden":"problem statement","content":"Consider the following rhythm‑action game on the real line.\n\n> 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.\n> 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.\n\nMs. AtCoder can move at speed $1$ on the line. Can she win the game? Pressing a button takes negligible time.\nSolve $\\mathrm{TESTCASES}$ test cases."},{"iden":"constraints","content":"*   $1 \\le \\mathrm{TESTCASES} \\le 100\\,000$\n*   $1 \\le N \\le 5\\,000$\n*   $0 \\le D \\le 10^{12}$\n*   $0 \\le T_1 \\le T_2 \\le \\dots \\le T_N \\le 10^{12}$\n*   $1 \\le X_i \\le 10^{12}$\n*   The sum of $N$ over all test cases is at most $100\\,000$.\n*   The sum of $N^2$ over all test cases is at most $2.5 \\times 10^7$.\n*   All input values are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format, where $\\mathrm{case}_k$ represents the $k$\\-th test case:\n\n$\\mathrm{TESTCASES}$\n$\\mathrm{case}_1$\n$\\mathrm{case}_2$\n $\\vdots$\n$\\mathrm{case}_{\\mathrm{TESTCASES}}$\n\nEach test case is given in the following format:\n\n$N$\n$D$\n$T_1$ $X_1$\n$T_2$ $X_2$\n $\\vdots$\n$T_N$ $X_N$"},{"iden":"sample input 1","content":"4\n2\n10\n30 20\n50 10\n2\n9\n30 20\n50 10\n4\n185\n0 40\n0 30\n0 20\n0 10\n5\n1312372641\n141421356 314159265\n237309504 358979323\n880168872 846264338\n4209698078 327950288\n5696718753 419716939"},{"iden":"sample output 1","content":"Yes\nNo\nYes\nNo\n\nFor the first test case, the game can be won as follows, so the first line contains `Yes`.\n\nElapsed time\n\nAction / Event\n\n$0$ seconds\n\nGame starts.\n\n$5$ seconds\n\nStart moving right from coordinate $0$.\n\n$25$ seconds\n\nArrive at coordinate $20$ and stop.\n\n$30$ seconds\n\nButton $1$ appears at coordinate $20$. Press it immediately and head left.\n\n$50$ seconds\n\nArrive at coordinate $0$. Head right. Button $2$ appears at coodinate $10$.\n\n$60$ seconds\n\nArrive at coordinate $10$ and press button $2$ (before it disappears at $60.5$ seconds).\n\nFor the second test case, the game is unwinnable, so the second line contains `No`.  \nFor the third test case, the game is winnable, so the third line contains `Yes`.  \nFor the fourth test case, the game is unwinnable, so the fourth line contains `No`."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}