Manage your Energy (Small)

Your calendar today is packed with important things to do. You prepared carefully, so none of the activities overlap. Now it is morning, and you are worried that your enthusiasm will run ahead of your energy.

You have to manage that energy. You start the day with a full tank of $E$ joules. You may never go below zero joules, or you drop from exhaustion. On each activity you may spend any non-negative integer number of joules (spend zero if you feel lazy), and after each activity you regain $R$ joules. No matter how lazy you are, your energy can never exceed $E$ joules, and any energy you would regain past that point is wasted.

Some things matter more than others. The $i$-th activity has a value $v_i$ that says how important it is to you. The gain from an activity is its value multiplied by the number of joules you spend on it. Manage your energy so that the total gain is as large as possible.

You cannot reorder the activities in your calendar. The order is fixed, and only the split of energy is up to you.

The first line contains the number of test cases $T$. $T$ test cases follow. Each test case is described by two lines.

The first line contains three integers $E$, $R$, and $N$. $E$ is the maximum and initial amount of energy, $R$ is the amount you regain after each activity, and $N$ is the number of activities planned for the day. The second line contains the values $v_1, v_2, \dots, v_N$ in order.

Limits

• $1 \le T \le 100$
• $1 \le E \le 5$
• $1 \le R \le 5$
• $1 \le N \le 10$
• $1 \le v_i \le 10$

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 maximum gain you can achieve by managing your energy that day.

In the first sample case you spend all 5 joules on the first activity for a gain of 10, regain 2, and spend them on the second activity. In the second case you spend 2 joules on the first activity, regain them, and spend 5 on the second. In the third case the regain rate equals the maximum energy, so the tank is full again after every activity and you can spend the full 3 joules on each of the four activities.