P13261 [GCJ 2014 #3] Last Hit

Diana 需要你的帮助，在她最喜欢的游戏中尽可能赚取更多金币。她经常会遇到这样一种情况：她站在自己的防御塔附近，面对着 $\mathbf{N}$ 个怪物。在这种情况下，Diana 和防御塔轮流攻击怪物，且 Diana 先手。在她的回合中，Diana 可以选择攻击任意一个怪物（也可以选择跳过回合）；在塔的回合中，塔会攻击距离它最近的存活怪物。 Diana 和塔都不能攻击已经死亡的怪物。 如果 Diana 攻击了某个怪物，则该怪物的生命值会减少 $\mathbf{P}$；如果塔攻击怪物，该怪物的生命值会减少 $\mathbf{Q}$。当怪物的生命值降到小于 1 时，它会被击杀。如果是 Diana 击杀了第 $i$ 个怪物，她将获得 $\mathbf{G}_{\mathrm{i}}$ 金币；如果是塔击杀了怪物，Diana 不会获得金币。 第 $i$ 个怪物初始生命值为 $\mathbf{H}_{\mathrm{i}}$。 怪物按照它们距离防御塔的远近顺序给出，也就是说，塔只有在编号小于 $i$ 的怪物都死亡之后，才会攻击第 $i$ 个怪物。 请你计算，Diana 最多可以获得多少金币？

输入的第一行是测试用例数量 $\mathbf{T}$。接下来是 $\mathbf{T}$ 个测试用例。 每个测试用例第一行包含三个用空格分隔的整数，分别表示 $\mathbf{P}$、$\mathbf{Q}$ 和 $\mathbf{N}$。 接下来的 $\mathbf{N}$ 行中，第 $i$ 行包含两个用空格分隔的整数，分别表示第 $i$ 个怪物的生命值 $\mathbf{H}_{\mathrm{i}}$ 和金币奖励 $\mathbf{G}_{\mathrm{i}}$。

对于每个测试用例，输出一行，格式为 `"Case #x: y"`，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是 Diana 最多可以获得的金币数。

**样例说明** 在第二个样例中，Diana 应该放弃第一个怪物。她应在前两个回合中攻击第三个怪物，将其生命值削减至 80 点，然后她就可以轻松地拿到对第二个和第三个怪物的最后一击，从而获得两者的金币奖励。 ## 限制条件 - $1 \leq T \leq 100$ - $20 \leq \mathbf{P} \leq 200$ - $20 \leq \mathbf{Q} \leq 200$ - $1 \leq \mathbf{H}_{\mathrm{i}} \leq 200$ - $0 \leq \mathbf{G}_{\mathrm{i}} \leq 10^6$ ### Small 数据集（10 分） - 时间限制：~~60~~ 3 秒 - $1 \leq \mathbf{N} \leq 4$ ### Large 数据集（14 分） - 时间限制：~~120~~ 5 秒 - $1 \leq \mathbf{N} \leq 100$ 翻译由 ChatGPT-4o 完成