Theme Park Roller Coaster

The roller coaster at the theme park has a line all day. Some people come alone. Others come as one group and will board only if the whole group rides together. Everyone who rides gets back in line afterwards, and a ride costs 1 Euro per person. Compute how much money the roller coaster takes in today.

The roller coaster seats at most $k$ people per ride. People queue in groups. Groups board one at a time from the front of the queue until no groups are left or the next group does not fit in the remaining seats, and then the coaster departs even if seats are empty. A smaller group standing further back never skips ahead. When the ride ends, the groups that rode return to the back of the queue in the order they boarded. The coaster runs $R$ times in a day.

Take $R = 4$, $k = 6$ and group sizes 1, 4, 2, 1 from the front. On the first ride the first two groups [1, 4] board and one seat stays empty. The group of 2 does not fit, and the group of 1 behind it cannot skip ahead. The queue is now 2, 1, 1, 4. The second ride carries [2, 1, 1], which is 4 people, and the queue becomes 4, 2, 1, 1. The third ride carries [4, 2], which is 6 people, and the queue becomes 1, 1, 4, 2. The fourth ride carries [1, 1, 4], which is 6 people. The day earns 21 Euros in total.

The first line contains the number of test cases $T$. Each test case then takes two lines. The first line contains three space separated integers $R$, $k$ and $N$. The second line contains $N$ space separated integers $g_0, g_1, \dots, g_{N-1}$, where $g_i$ is the size of the $i$-th group in queue order.

Limits

• $1 \le T \le 50$
• $1 \le R \le 10^8$
• $1 \le k \le 10^9$
• $1 \le N \le 1000$
• $1 \le g_i \le 10^7$
• $g_i \le k$ for every $i$

For each test case, print one line in the form Case #x: y, where $x$ is the test case number starting from 1 and $y$ is the number of Euros the roller coaster earned that day.