你今天日程排得很满，有很多重要的事情要做。你努力做了准备，确保所有活动的时间互不冲突。现在是早晨，你担心尽管你充满热情，但可能没有足够的精力全身心投入到所有活动中。

你需要仔细管理你的精力。你一天开始时精力充沛，确切地说是拥有 $E$ 焦耳的精力。你知道你的精力不能低于零，否则你会因精疲力竭而倒下。在每项活动中，你可以花费任意非负整数焦耳的精力（如果你觉得懒，也可以花费零焦耳），并且在每项活动结束后，你会恢复 $R$ 焦耳的精力。无论你多么懒散，你的精力在任何时候都不能超过 $E$ 焦耳；任何超过该上限的恢复精力都会被浪费掉。

现在，有些事情（比如解决 Code Jam 问题）比其他事情更重要。对于第 $i$ 项活动，你有一个值 $v_i$，表示这项活动对你有多重要。你从每项活动中获得的“收益”是该活动的值乘以你在该活动上花费的精力（以焦耳为单位）。你希望管理好你的精力，使得总收益尽可能大。

请注意，你不能重新安排日程表中的活动顺序。你只能在现有的日程安排下尽可能好地管理你的精力。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例由两行组成。第一行包含三个整数：$E$（最大精力及初始精力）、$R$（每项活动后恢复的精力）和 $N$（当天计划的活动数量）。第二行包含 $N$ 个整数 $v_i$，描述了你今天计划的各项活动的值。

输出格式

对于每个测试用例，输出一行 "Case #$x$: $y$"，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是你通过管理精力所能获得的最大收益。

数据范围

$1 \le T \le 100$。

小数据集（测试集 1 - 可见；12 分）

$1 \le E \le 5$ $1 \le R \le 5$ $1 \le N \le 10$ $1 \le v_i \le 10$

大数据集（测试集 2 - 隐藏；23 分）

$1 \le E \le 10^7$ $1 \le R \le 10^7$ $1 \le N \le 10^4$ $1 \le v_i \le 10^7$

样例

样例输入 1

3
5 2 2
2 1
5 2 2
1 2
3 3 4
4 1 3 5

样例输出 1

Case #1: 12
Case #2: 12
Case #3: 39

说明

在第一个案例中，我们可以将全部 5 焦耳精力花费在第一项活动上（收益为 10），恢复 2 焦耳后再将其花费在第二项活动上。在第二个案例中，我们在第一项活动上花费 2 焦耳，恢复后在第二项活动上花费 5 焦耳。在第三个案例中，我们的恢复速率等于最大精力，这意味着我们在每项活动后总是能恢复全部精力，因此我们可以在每项活动上都花费全部 3 焦耳的精力。