Theme Park (Small)

The roller coaster is the most popular ride in this park. Some visitors come alone and some come as a group, and a group rides only when every member of the group rides together. Everyone who has ridden once wants another turn, so a group goes straight back to the queue after getting off. A ride costs 1 euro per person. Predict how much the roller coaster earns today.

The coaster seats at most $k$ people per run. The groups wait in a queue and board in order, starting from the front. It departs once every group has boarded, or once the next group in line no longer has enough free seats for all of its members, even if seats are still empty. A group never passes the group ahead of it. After the run the groups rejoin the back of the queue in the order they boarded. The coaster departs $R$ times a day.

For example, let $R = 4$ and $k = 6$, with four groups of 1, 4, 2 and 1 people standing in that order. The first run takes the group of 1 and the group of 4, then leaves with one empty seat, because the group of 2 does not fit and the last group of 1 cannot pass it. Those two groups return to the back, so the queue becomes 2, 1, 1, 4. The second run carries 2, 1 and 1, so 4 riders, and the queue becomes 4, 2, 1, 1. The third run carries 4 and 2, so 6 riders, and the queue becomes 1, 1, 4, 2. The last run carries 1, 1 and 4, so 6 riders. The day earns 21 euros.

The first line contains the number of test cases $T$. The $T$ test cases follow, two lines each. The first line holds three integers $R$, $k$ and $N$ separated by spaces. The second line holds $N$ integers $g_0, g_1, \dots, g_{N-1}$ separated by spaces, where $g_i$ is the size of the $(i+1)$-th group in the queue.

Constraints

• $1 \le T \le 50$
• $1 \le R \le 1000$
• $1 \le k \le 100$
• $1 \le N \le 10$
• $1 \le g_i \le 10$
• $g_i \le k$

For each test case print one line in the form Case #X: Y, where $X$ is the test case number starting at 1 and $Y$ is the roller coaster's earnings for that day.