题目描述

Cloud Retainer, the builder of the Dwelling in the clouds above Qingyun Peak, is very interested in mechanics. Although there is more than one month away from the Lantern Rite Festival in Liyue, she has already started the design of a gaming event for it.

The game is mainly about releasing pinballs to get a score as high as possible. It is played on the 2-dimensional plane with two horizontal straight lines $y = 0$ and $y = H$. Between the two lines, there are $n$ tiny wooden boards and $m$ coins, both can be regarded as single points. The $i$-th wooden board is located at $(x_i, y_i)$ while the $i$-th coin is located at $(x'_i, y'_i)$.

A pinball is released from $(10^{-9}, 10^{-9})$ by the player. Let $\overrightarrow{v} = (v_x, v_y)$ be the velocity of the ball (that is to say, if the ball is currently located at $(x, y)$ it will move to $(x + v_x\epsilon, y + v_y\epsilon)$ after $\epsilon$ seconds). Initially $\overrightarrow{v} = (1, 1)$.

When the ball hits a wooden board or one of the two horizontal straight lines, $v_y$ will be negated (that is, $v_y$ becomes $-v_y$) while $v_x$ remains unchanged. If the ball hits a coin, the player's score is increased by $1$ and the velocity of the ball remains unchanged.

To gain a higher score, the player can choose to remove any number of wooden boards before the pinball is released. It is also OK not to remove any wooden board. Cloud Retainer wants you to help her estimate the difficulty by computing the maximum score the player can get after $10^{10^{10^{10^{10}}}}$ seconds under the best strategy?

输入格式

There are multiple test cases. The first line of the input contains an integer $T$ indicating the number of test cases. For each test case:

The first line contains one integer $H$ ($2 \le H \le 10^9$).

The second line contains one integer $n$ ($1 \le n \le 10^5$) indicating the number of wooden boards.

For the following $n$ lines, the $i$-th line contains two integers $x_i$ and $y_i$ ($1 \le x_i \le 10^9$, $1 \le y_i < H$) indicating a wooden board located at $(x_i, y_i)$.

The following line contains one integer $m$ ($1 \le m \le 10^5$) indicating the number of coins.

For the following $m$ lines, the $i$-th line contains two integers $x'_i$ and $y'_i$ ($1 \le x'_i \le 10^9$, $1 \le y'_i < H$) indicating a coin located at $(x'_i, y'_i)$.

It's guaranteed that the given $(n + m)$ points in the same test case will be distinct. It's also guaranteed that neither the sum of $n$ nor the sum of $m$ of all test cases will exceed $5 \times 10^5$.

输出格式

For each test case output one line containing one integer indicating the maximum score the player can get after removing some (or not removing any) wooden boards.

题目大意

参考题中所给图片，有上下两根直线，之间的距离为 $H$，还有 $n$ 个镜子，可以反射光线，也可以让其穿过，有 $m$ 个物品，一开始有一束从原点出发四十五度向右上方射出的一条光线，请你控制每个镜子的开关，求这条光线最多能经过几个物品。

——By @紊莫

2
4
3
1 1
2 2
6 2
4
3 1
3 3
5 1
7 3
3
1
4 2
3
1 1
6 2
9 1

3
3

提示

The two sample test cases are shown below. Solid diamonds represent the remaining wooden boards, while hollow diamonds represent the removed wooden boards and round dots represent the coins.