Diana 需要你的帮助，以便在她最喜欢的游戏中获得尽可能多的金币。她经常面临这样一种场景：她站在塔附近，面对着 $N$ 只怪物。在这种情况下，Diana 和塔轮流射击怪物，Diana 先手。在她的回合中，Diana 可以选择射击一只怪物（这意味着 Diana 也可以选择跳过回合）。在塔的回合中，塔会射击距离它最近的怪物。Diana 和塔都不能射击已经死亡的怪物。

如果 Diana 射击一只怪物，其生命值减少 $P$。如果塔射击一只怪物，其生命值减少 $Q$。如果怪物的生命值降至 1 以下，它就会死亡。第 $i$ 只怪物初始有 $H_i$ 点生命值。如果 Diana 的射击杀死了第 $i$ 只怪物，她将获得 $G_i$ 金币；如果塔的射击杀死了它，则她无法获得金币。Diana 最多能获得多少金币？

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个用例的第一行包含三个空格分隔的整数，分别表示 $P$、$Q$ 和 $N$。接下来的 $N$ 行中，第 $i$ 行包含两个空格分隔的整数，分别表示 $H_i$ 和 $G_i$。

怪物按距离塔的远近顺序给出。换句话说，塔只有在所有编号小于 $i$ 的怪物都死亡后，才会射击第 $i$ 只怪物。

输出格式

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

样例

输入格式 1

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

输出格式 1

Case #1: 300
Case #2: 500

说明

在第二个样例中，Diana 应该放弃第一只怪物。在她的前两个回合中，她应该削弱第三只怪物，将其生命值降至 80，从而使她能够轻松地对第二只和第三只怪物完成最后一击。