Problem Statement

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.

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.

Input

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

Output

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.