P13389 [GCJ 2010 Qualification] Theme Park

过山车真有趣！似乎每个来到主题公园的人都想乘坐过山车。有些人单独前来；有些人则结伴而来，并且他们不愿意分开，必须一起上车。每个乘坐过山车的人都想再玩一次。每人每次乘坐需要支付 $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$ 欧元。

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

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

**样例说明** - $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 翻译