Description

过山车真有趣！似乎每个来到主题公园的人都想乘坐过山车。有些人单独前来；有些人则结伴而来，并且他们不愿意分开，必须一起上车。每个乘坐过山车的人都想再玩一次。每人每次乘坐需要支付 $1$ 欧元；你的任务是计算今天过山车能赚多少钱。

过山车每次最多可容纳 $k$ 人。人们按组排队等候。每次上车时，按顺序让一个个小组上车，直到没有剩余小组或下一个小组无法全部上车为止；然后过山车就会出发，无论是否坐满。每次游玩结束后，所有乘客会按照原顺序重新排到队伍末尾。过山车一天会运行 $R$ 次。

例如，假设 $R=4$，$k=6$，有四个小组，人数分别为：$1$、$4$、$2$、$1$。第一次运行时，前两个小组 $[1, 4]$ 上车，还剩一个空位（$2$ 人的小组无法全部上车，$1$ 人的小组不能插队）。然后这两个小组排到队尾，队伍变为 $2$、$1$、$1$、$4$。第二次运行时，$[2, 1, 1]$ 共 $4$ 人上车。此时队伍变为 $4$、$2$、$1$、$1$。第三次运行时，$[4, 2]$ 共 $6$ 人上车。此时队伍变为 $[1, 1, 4, 2]$。最后一次运行时，$[1, 1, 4]$ 共 $6$ 人上车。最终，过山车一共赚了 $21$ 欧元。

Input Format

输入的第一行包含测试用例数 $T$。接下来有 $T$ 组测试数据，每组测试数据包含两行。第一行包含三个用空格分隔的整数：$R$、$k$ 和 $N$。第二行包含 $N$ 个用空格分隔的整数 $g_{i}$，每个 $g_{i}$ 表示一个小组的人数。$g_{0}$ 是第一个小组的人数，$g_{1}$ 是第二个小组的人数，依此类推。

Output Format

对于每组测试数据，输出一行，格式为 "Case #x: y"，其中 $x$ 表示测试用例编号（从 $1$ 开始），$y$ 表示过山车赚到的欧元数。

3
4 6 4
1 4 2 1
100 10 1
1
5 5 10
2 4 2 3 4 2 1 2 1 3

Case #1: 21
Case #2: 100
Case #3: 20

Hint

样例说明

• $1 \leqslant T \leqslant 50$。
• $g_{i} \leqslant k$。

小数据范围（10 分，测试点 1 - 可见）

• $1 \leqslant R \leqslant 1000$。
• $1 \leqslant k \leqslant 100$。
• $1 \leqslant N \leqslant 10$。
• $1 \leqslant g_{i} \leqslant 10$。

大数据范围（23 分，测试点 2 - 隐藏）

• $1 \leqslant R \leqslant 10^{8}$。
• $1 \leqslant k \leqslant 10^{9}$。
• $1 \leqslant N \leqslant 1000$。
• $1 \leqslant g_{i} \leqslant 10^{7}$。

由 ChatGPT 4.1 翻译