Background

Enhanced version: “NAPC #1” rStage3 ~ Hard Jump Refreshers。

---

Problem Description

(Note that in this problem, kid’s movement is different from that in the real iw game.)

In front of kid there is an infinite vertical 2D plane. The positive direction of the $x$ axis is from left to right, and the positive direction of the $y$ axis is from bottom to top.

On the map (this plane), there are $n$ jump orbs at pairwise distinct positions, and each orb can be used infinitely many times. When kid is exactly at the position of a jump orb, he can hold down the shift key, and then he will instantly rise by $d$ cells (during this process he cannot move left or right). He falls downward by $1$ cell per second. Also, each second kid may choose to move 1 cell to the left, move 1 cell to the right, or not move. When kid is not on a jump orb, he cannot jump.

The figure above is an example. The blue region indicates the area kid can reach after jumping at a jump orb (the arrow) with $d=2$. kid’s horizontal and vertical coordinates at each second must be integers, i.e., we assume he cannot reach non-integer grid points.

Now, kid saved the game at the $c$-th jump orb (so the starting point is the $c$-th jump orb; he can jump immediately). Define kid’s score as the number of distinct jump orbs he has visited (i.e., he jumps at that position; obviously after jumping he may return to the original position). kid wants to know the maximum score he can obtain (he does not need to, but may, return to the start). Please tell him.

Note again: jump orbs can be used infinitely many times, i.e., kid may jump at the same jump orb infinitely often。

Input Format

This problem contains multiple test cases in one input file.

The first line contains two integers $T,id$, denoting the number of test cases and the test point id. In particular, for the samples, $id=0$.

For each test case:

The first line contains three positive integers $n,d,c$ as described above.

The next $n$ lines each contain two positive integers $x_i,y_i$, denoting the position of the $i$-th jump orb.

Output Format

For each test case, output one line with one positive integer, the maximum score.

4 0
4 2 1
2 4
1 1
5 2
4 1
5 3 4
1 7
2 4
3 2
4 5
8 2
4 1 2
1 1
1 2
1 3
4 1
4 2 1
1 1
4 1
1 4
4 4

3
4
4
1

Hint

Constraints

This problem uses bundled subtasks.

$$\def\r{\cr\hline} \def\None{\text{None}} \def\arraystretch{1.5} \begin{array}{c|c|c|c} \textbf{Subtask} & id= & \textbf{Sp. Constraints} & \textbf{Score}\r \textsf1& 1\sim3,36 & n\leqslant10,T\leqslant10 & 10 \r \textsf2& 4\sim7 & \sum n\leqslant200 & 15 \r \textsf3& 8\sim13 & \mathbf A & 25 \r \textsf4& 14\sim18 & \mathbf B & 10 \r \textsf5& 19\sim35 & - & 40 \r \end{array}$$

Here, $\sum n$ denotes the sum of $n$ over all test cases within a single test point.

• Special property $\mathbf A$: For any two different jump orbs $u,v$, if kid can theoretically jump from $u$ to $v$ (theoretically: ignoring whether kid can reach $u$ from the starting point; same below), then he theoretically must not be able to jump from $v$ to $u$.
• Special property $\mathbf B$: For any jump orbs $u,v$, if kid can theoretically jump from $u$ to $v$, then he theoretically must be able to jump from $v$ to $u$.

Note that “jump from $u$ to $v$” does not have to be done in a single jump. For example, in Sample #1-2 you can jump from the 3rd to the 5th: $3\to2\to4\to5$.

For $100\%$ of the data, $1\leqslant T\leqslant 1000$，$1\leqslant n\leqslant 3000$，$\sum n\leqslant 3000$，$1\leqslant d\leqslant 10^9$，$1\leqslant c\leqslant n$，$1\leqslant x_i,y_i\leqslant10^6$，$(x_i,y_i)$ are pairwise distinct.

---

Sample Explanation #1-1

With $d=2$, it is easy to see that once you leave the initial position, you cannot get back up. So kid either goes left to touch the 2nd jump orb, getting a score of $2$; or he jumps to the right, visiting the 3rd and 4th jump orbs, getting a score of $3$.

Sample Explanation #1-2

With $d=3$, kid can first go down in a loop ($4\to3\to2\to4$) and jump back to the starting point, then go right to touch the 5th orb. The 1st jump orb in the upper left corner cannot be reached.

Sample Explanation #1-3

You can jump to the right by passing through the topmost orb.

Sample Explanation #1-4

Some people are alive……

Translated by ChatGPT 5