P9848 [ICPC 2021 Nanjing R] Cloud Retainer's Game

云堇，青云峰上云中居的建造者，对机械非常感兴趣。虽然距离璃月的海灯节还有一个多月的时间，她已经开始为其设计一个游戏活动。 游戏主要是关于释放弹珠以获得尽可能高的分数。它在二维平面上进行，平面上有两条水平直线 $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$。

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

下面显示了两个示例测试用例。实心菱形表示剩余的木板，空心菱形表示被移除的木板，圆点表示硬币。 题面翻译由 ChatGPT-4o 提供。