题目描述

青云峰云中居的建造者云留客对力学非常感兴趣。虽然距离漓江的元宵灯会还有一个多月的时间，但她已经开始设计元宵灯会的游戏活动了。

这款游戏主要是通过释放弹球来获得尽可能高的分数。游戏在二维平面上进行，平面上有两条水平直线 $y = 0$ 和 $y = H$。两条直线之间有 $n$ 块小木板和 $m$ 枚硬币，两者均可视为单点。$i$ 个木板位于 $(x_i, y_i)$，而 $i$ 个硬币位于 $(x'_i, y'_i)$。

玩家从 $(10^{-9}, 10^{-9})$ 释放一个弹球。假设 $\overrightarrow{v} = (v_x, v_y)$ 是弹球的速度（也就是说，如果弹球当前位于 $(x, y)$，那么它将在 $\epsilon$ 秒后移动到 $(x + v_x\epsilon, y + v_y\epsilon)$。初始值为 $\overrightarrow{v} = (1, 1)$。

当小球击中木板或两条水平直线之一时，$v_y$ 将被取反（即 $v_y$ 变为 $-v_y$，而 $v_x$ 保持不变。如果小球击中一枚硬币，玩家的得分将增加 $1$，而小球的速度保持不变。

为了获得更高的分数，玩家可以选择在弹球释放前移除任意数量的木板。也可以不移除任何木板。云留客希望您帮助她估算难度，计算在最佳策略下，玩家在 $10^{10^{10^{10^{10}}}}$ 秒后能获得的最高分？

输入格式

有多个测试用例。输入的第一行包含一个整数 $T$，表示测试用例的数量。对于每个测试用例：

第一行包含一个整数 $H$（$2 \le H \le 10^9$）。

第二行包含一个整数 $n$（$1 \le n \le 10^5$），表示木板的数量。

在接下来的 $n$ 行中，第 $i$ 行包含两个整数 $x_i$ 和 $y_i$（$1 \le x_i \le 10^9$，$1 \le y_i < H$），表示木板位于 $(x_i, y_i)$ 处。

下面一行包含一个整数 $m$（$1 \le m \le 10^5$），表示硬币的数量。

在接下来的 $m$ 行中，第 $i$ 行包含两个整数 $x'_i$ 和 $y'_i$（$1 \le x'_i \le 10^9$，$1 \le y'_i < H$），表示一枚硬币位于 $(x'_i, y'_i)$ 处。

可以保证同一测试用例中给出的 $(n + m)$ 个点是不同的。同时保证所有测试用例中 $n$ 和 $m$ 的总和都不会超过 $5 \times 10^5$。

输出格式

对每个测试用例输出一行，其中包含一个整数，表示玩家在移除一些（或不移除任何）木板后能得到的最高分。

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

解释 #1

两个测试案例示例如下。实心菱形代表剩余的木板，空心菱形代表移走的木板，圆点代表硬币。