题目描述

Roller coasters are so much fun! It seems like everybody who visits the theme park wants to ride the roller coaster. Some people go alone; other people go in groups, and don't want to board the roller coaster unless they can all go together. And everyone who rides the roller coaster wants to ride again. A ride costs 1 Euro per person; your job is to figure out how much money the roller coaster will make today.

The roller coaster can hold $k$ people at once. People queue for it in groups. Groups board the roller coaster, one at a time, until there are no more groups left or there is no room for the next group; then the roller coaster goes, whether it's full or not. Once the ride is over, all of its passengers re-queue in the same order. The roller coaster will run $R$ times in a day.

For example, suppose $R=4$, $k=6$, and there are four groups of people with sizes: $1$, $4$, $2$, $1$. The first time the roller coaster goes, the first two groups $[1, 4]$ will ride, leaving an empty seat (the group of $2$ won't fit, and the group of $1$ can't go ahead of them). Then they'll go to the back of the queue, which now looks like $2$, $1$, $1$, $4$. The second time, the coaster will hold $4$ people: $[2, 1, 1]$. Now the queue looks like $4$, $2$, $1$, $1$. The third time, it will hold $6$ people: $[4, 2]$. Now the queue looks like $[1, 1, 4, 2]$. Finally, it will hold $6$ people: $[1, 1, 4]$. The roller coaster has made a total of $21$ Euros!

输入格式

The first line of the input gives the number of test cases, $T$. $T$ test cases follow, with each test case consisting of two lines. The first line contains three space-separated integers: $R$, $k$ and $N$. The second line contains $N$ space-separated integers $g_{i}$, each of which is the size of a group that wants to ride. $g_{0}$ is the size of the first group, $g_{1}$ is the size of the second group, etc.

输出格式

For each test case, output one line containing "Case #x: y", where $x$ is the case number (starting from $1$) and $y$ is the number of Euros made by the roller coaster.

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

提示

Sample Explanation

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

Small dataset (10 Pts, Test set 1 - Visible)

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

Large dataset (23 Pts, Test set 2 - Hidden)

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