Manage Your Energy

Problem

Your calendar today is packed with important things to do. You worked hard to make sure none of the activities overlap. Now it is morning, and you are worried that despite all your enthusiasm you will not have the energy to do all of this with full engagement.

You have to manage your energy carefully. You start the day with your maximum energy, $E$ joules. You can never go below zero joules, or you drop from exhaustion. You can spend any non-negative integer number of joules on each activity, including zero if you feel lazy, and after each activity you regain $R$ joules of energy. No matter how lazy you are, your energy can never exceed $E$ joules at any moment. 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 one activity is its value multiplied by the amount of energy, in joules, you spend on it. Manage your energy so that your total gain is as large as possible.

You cannot reorder the activities in your calendar. The order stays fixed and you only decide how to split your energy.

Input

The first line contains the number of test cases $T$ . $T$ test cases follow, each described by two lines.

The first line of a test case 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 calendar order.

Limits

$1 \le T \le 100$
$1 \le E \le 10^7$
$1 \le R \le 10^7$
$1 \le N \le 10^4$
$1 \le v_i \le 10^7$

Output

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. The answer fits in a 64-bit signed integer.

Note

In the first case of the example, you spend all 5 joules on the first activity for a gain of 10, regain 2 joules, and spend them on the second activity. In the second case, you spend 2 joules on the first activity, regain those 2 joules, and spend 5 on the second. In the third case, the regain amount equals the maximum energy, so your energy is full again after every activity and you can spend the full 3 joules on each one.