P15360 "WYZOI R2" Fireworks

During the Spring Festival, Little S plans to hold a grand fireworks show. The trajectory of a firework can be represented by a polyline $L$. You already know that the polyline $L$ is formed by connecting these $n$ points in order: $(x_1,y_1),(x_2,y_2),\dots,(x_n,y_n)$. It is guaranteed that $x_1

**Each test point contains multiple test cases.** The first line of the input contains a positive integer $T$, representing the number of test cases. For each test case: The first line contains two non-negative integers $n,d$, representing the number of points and the parameter given by Little S. The second line contains $n$ non-negative integers $x_1,x_2,\dots,x_n$, where $x_i$ denotes the $x$-coordinate of the $i$-th point. The third line contains $n$ non-negative integers $y_1,y_2,\dots,y_n$, where $y_i$ denotes the $y$-coordinate of the $i$-th point.

For each test case, output one line with one integer, representing the maximum number of points that can be deleted.

**[Sample Explanation]**  For the first test case, one valid solution is to delete the points $(1,2),(2,2),(5,3)$. In the picture, the black line is the polyline $L$ before deletion, the red line is the polyline $L'$ after deletion, and the blue line is the common part of $L$ and $L'$. For each $p$, the points $(p,L(p))$ and $(p,L'(p))$ are both marked in the picture. Specifically, the values of $L(p)$ and $L'(p)$ for different $p$ are listed as follows. It is easy to verify that all values of $|L(p)-L'(p)|$ are no more than $1$. |$p=$|$0$|$1$|$2$|$3$|$4$|$5$|$6$|$7$|$8$| |:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:| |$L(p)=$|$0$|$2$|$2$|$4$|$\frac{7}{2}$|$3$|$\frac{3}{2}$|$0$|$3$| |$L'(p)=$|$0$|$\frac{4}{3}$|$\frac{8}{3}$|$4$|$3$|$2$|$1$|$0$|$3$| **[Constraints]** **This problem uses bundled tests.** | Subtask ID | $n\le$ | Special Properties | Score | | :-----: | :---: | :--: | :--: | | $0$ | $15$ | $T\le 10,x_n\le 30$ | $15$ | | $1$ | $100$ | $T\le 10,x_n\le 200$ | $20$ | | $2$ | $100$ | $T\le 10$ | $20$ | | $3$ | $5000$ | $x_n\le 10^4$ | $20$ | | $4$ | $5000$ | None | $25$ | For $100\%$ of the testdata, it is guaranteed that $1\le T\le 10^3$, $2 \le n \le 5 \times 10^3$, $0\le d,x_i,y_i \le 10^9$, $x_1