Description

你今天的日程非常繁忙，安排了许多重要的事情要做。你已经努力做好准备，确保所有活动之间不会重叠。现在早晨到来，尽管你充满热情，但你担心自己的精力不足以全身心投入到所有活动中。

你必须谨慎地管理自己的能量。你一开始拥有充沛的精力——准确地说，是 $E$ 焦耳。你知道自己不能让能量低于 $0$ 焦耳，否则你会因精疲力竭而倒下。你可以在每项活动上花费任意非负整数数量的能量（如果你很懒，也可以花费 $0$），每完成一项活动后，你会恢复 $R$ 焦耳的能量。但无论你多么懒惰，你在任何时刻能拥有的能量都不会超过 $E$ 焦耳；如果恢复后能量超过 $E$，则超出的部分会被浪费。

有些事情（比如解决 Code Jam 问题）比其他事情更重要。对于第 $i$ 个活动，你有一个价值 $v_i$，表示这项活动对你的重要程度。你从每项活动中获得的收益等于活动价值与你在该活动上花费的能量（单位：焦耳）的乘积。你希望通过合理分配能量，使得总收益尽可能大。

注意，你不能调整日程中活动的顺序。你只能在既定顺序下尽量合理地管理能量。

Input Format

输入的第一行为测试用例数量 $T$。接下来有 $T$ 个测试用例。每个测试用例包含两行。第一行为三个整数：$E$，即最大（也是初始）能量值，$R$，即每次活动之后恢复的能量值，以及 $N$，表示当天计划的活动数。第二行为 $N$ 个整数 $v_i$，表示你今天计划的各项活动的价值。

Output Format

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

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

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

Hint

样例解释

在第一个样例中，我们可以在第一个活动上花费全部 $5$ 焦耳（收益为 $10$），恢复 $2$ 焦耳后，在第二个活动上花费这 $2$ 焦耳。在第二个样例中，我们在第一个活动上花费 $2$ 焦耳，恢复 $2$，然后在第二个活动上花费 $5$。在第三个样例中，恢复速度等于最大能量，因此每次活动后都能恢复满能量——所以每次都可以用满 $3$ 焦耳。

限制条件

• $1 \leq T \leq 100$

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

• $1 \leq E \leq 5$
• $1 \leq R \leq 5$
• $1 \leq N \leq 10$
• $1 \leq v_i \leq 10$

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

• $1 \leq E \leq 10^7$
• $1 \leq R \leq 10^7$
• $1 \leq N \leq 10^4$
• $1 \leq v_i \leq 10^7$

翻译由 ChatGPT-4.1 完成。