Description

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 最多可以获得多少金币？

Input Format

输入的第一行是测试用例数量 $\mathbf{T}$。接下来是 $\mathbf{T}$ 个测试用例。

每个测试用例第一行包含三个用空格分隔的整数，分别表示 $\mathbf{P}$、$\mathbf{Q}$ 和 $\mathbf{N}$。

接下来的 $\mathbf{N}$ 行中，第 $i$ 行包含两个用空格分隔的整数，分别表示第 $i$ 个怪物的生命值 $\mathbf{H}_{\mathrm{i}}$ 和金币奖励 $\mathbf{G}_{\mathrm{i}}$。

Output Format

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

2
20 40 3
100 100
20 100
60 100
20 60 3
80 100
80 200
120 300

Case #1: 300
Case #2: 500

Hint

样例说明

在第二个样例中，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 完成