Problem Description

In a 2D Cartesian coordinate system, there are $n$ beans, where the $i$-th bean has coordinates $(x_i, y_i)$.

Define a black hole as a segment parallel to the $x$-axis with a length of $k$. Specifically, if $k = 0$, the black hole becomes a single point.

After the game starts, all the beans will continuously move in the negative $y$-axis direction (i.e., downward).

You have two black holes, and you can place them anywhere (including at negative coordinates) to catch the beans. If at any moment a bean encounters a black hole, it is caught and stops moving. If a bean can never encounter a black hole, it is lost.

Your task is to design a placement strategy for the black holes to maximize the number of beans caught. Output the maximum number of beans caught.

Input Format

Read the data from the file bean.in.

Each test contains multiple test cases.

The first line contains two positive integers $c, T$, representing the test case ID and the number of test cases.

For each of the $T$ test cases:

• The first line contains two positive integers $n, k$, the number of beans and the length of the black hole.
• The next $n$ lines each contain two integers $x_i, y_i$, the coordinates of a bean.

Output Format

Output to the file bean.out.

For each test case, output a single integer on a new line, representing the maximum number of beans that can be caught.

Samples

1 1
8 2
1 1
1 2
2 5
4 4
5 3
6 2
6 4
7 3

7

【Sample #1 Explanation】

The left endpoints of the two black holes can be positioned at $(0,0)$ and $(4,1)$, as shown in the diagram below:

The red dots represent the beans that can be caught, totaling 7. This is one of the optimal solutions.

【Sample #2】

See the attached files bean/bean2.in and bean/bean2.ans。

This sample satisfies the properties of Test Case #1.

【Sample #3】

See the attached files bean/bean3.in and bean/bean3.ans。

This sample satisfies the properties of Test Case #2.

【Sample #4】

See the attached files bean/bean4.in and bean/bean4.ans。

This sample satisfies the properties of Test Case #4.

【Sample #5】

See the attached files bean/bean5.in and bean/bean5.ans。

This sample satisfies the properties of Test Case #6.

【Sample #6】

See the attached files bean/bean6.in and bean/bean6.ans。

This sample satisfies the properties of Test Case #8.

Constraints

For all data, it is guaranteed that:

• $1 \le T \le 5$
• $1 \le n \le 10^5$
• $0 \le k \le 10^9$
• $1 \le x_i,y_i \le 10^9$

Test ID	$n \le$	$k \le$	$x_i,y_i \le$	Special Properties
$1$	$10$			No
$2 \sim 3$	$10^5$	$0$	$10^9$
$4 \sim 5$		$10^9$		Yes
$6 \sim 7$	$10^3$			No
$8 \sim 10$	$10^5$	$10^9$

Special Properties：Number of different $x$-coordinates $\le 3$.

Attachment Download

link