407502: GYM102803 F False God

You are facing an endgame of Shogi.

You have only one Kin(金将). However, your opponent has $$$n$$$ Fu(步兵).

The rule of this game is as following.

If Kin is at $$$(x,y)$$$, it can move to one of the following positions in one step: $$$(x+1,y), (x+1,y+1), (x,y+1), (x-1,y+1), (x-1,y), (x,y-1)$$$.

If Fu is at $$$(x,y)$$$, it can only move to $$$(x,y-1)$$$ in one step.

Now you know the initial position of your Kin and your opponent's Fu. Each turn, you move your Kin first and then all Fu will move one step.

When you are moving Kin, you can defeat the Fu at that position. If one Fu moves one step and meets Kin, your opponent is also defeated.

To win this game, you want to defeat Fu as many as possible. Now Chino wonders the maximum count of Fu that will be defeated. Can you help cute Chino?

The first line contains one integer $$$T ~ (1 \leq T \leq 10)$$$ denoting the number of testcases.

For each testcase,

The first line contains two integers $$$x_0, y_0 ~ (|x_0|, |y_0| \leq 1\,000\,000\,000)$$$ denoting the initial position for Kin.

The second line contains one integer $$$n ~ (1 \leq n \leq 1\,000)$$$ denoting the number of Fus your opponent has.

The next $$$n$$$ lines each contains two integers $$$x_i, y_i ~ (|x_i|, |y_i| \leq 1\,000\,000\,000)$$$ denoting the position of Fu $$$i ~ (1 \leq i \leq n)$$$.

It is guaranteed that $$$(x_i, y_i) \neq (x_j, y_j)$$$ for all pairs of $$$i, j$$$ satisfying $$$0 \leq i < j \leq n$$$.

It is guaranteed that $$$\sum n \leq 5000$$$.

One line for each testcase with one integer denoting the answer.

2
1 1
2
0 2
2 2
2 1
5
0 0
2 0
3 3
5 4
4 6

1
4

For the second testcase, your Kin can defeat the last 4 Fu.