Theme Park (Small)

The roller coaster holds $k$ people at once. People queue for it in groups, and a group only boards if all of its members can ride together.

Boarding goes group by group from the front of the queue. If the next group fits in the remaining seats, it boards and the next group is considered. If the next group does not fit, boarding stops there, and a smaller group further back never jumps ahead. Once no group is left or the next group does not fit, the coaster departs even with empty seats.

Everyone who rides wants to ride again, so the passengers rejoin the back of the queue in the same order they boarded. The coaster runs $R$ times a day and a ride costs 1 Euro per person. Compute how much money the coaster makes in a day.

Take $R = 4$, $k = 6$, and four groups of sizes 1, 4, 2, 1 in that order. On the first run the first two groups, 1 and 4, ride and one seat stays empty: the group of 2 does not fit, and the group of 1 behind it cannot jump ahead. The queue is now 2, 1, 1, 4. On the second run the groups 2, 1, 1 ride, carrying 4 people, and the queue becomes 4, 2, 1, 1. On the third run the groups 4 and 2 ride, carrying 6 people, and the queue becomes 1, 1, 4, 2. On the last run the groups 1, 1, 4 ride, carrying 6 people. The coaster makes 21 Euros that day.

The first line contains the number of test cases $T$.

Each test case consists of 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 group standing $i+1$ from the front of the queue.

Limits

• $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 from 1 and $y$ is the number of Euros the coaster makes.