Mission Possible
Time Limit: 36000/18000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 147 Accepted Submission(s): 7
Problem Description
Mr. Frog loves playing video games. However, it seems that he does not have enough gift in this field, so he often gets stuck in some certain levels. Now this annoying situation comes to him again.
In this mission, Mr. Frog is asked to pass a
dangerous region which is currently under his enemies, control. Every second he is inside this region, his enemies would attack him with everything they have. Luckily, he is wearing a powersuit and still have time to enhance it.
powersuit has three main attributes： health point, velocity and recover speed. In the begin¬ning of this mission, the powersuit has H health points, and is able to move at no faster than Vm/s. Once the health point of powersuit is less than 0, the powersuit would be totally destroyed and Mr. Frog would immediately be killed. At the end of every second that the powersuit still works, the suit would repair itself and recover R health points.
After precise calculation, Mr. Frog has found that, to go through this area, he needs to run at least D meters distance, and every second his enemies, attack would cause A health point loss. Note that attacks take place all the time while the recover only happens at the end of every second, so you can consider that, in every whole second, the powersuit first loses A health points and then recovers R health points at the end of it, if it still works at that moment.
Mr. Frog could enhance his powersuit at any time he wants during the mission. At the beginning all three attributes of his powersuit equals to 0. He needs to pay $G_1$ in order to increase H by 1, while $G_2$ to increase V by 1 and $G_3$ to increase R by 1. For any of these three values, he can only increase it by non-negative integer. For some well-known reasons, Mr. Frog does not want to finish the game too quickly, so you cannot increase the powersuit's speed to more than D m/s. Since you looks so clever, now Mr. Frog wants to know not only how he can finish this mission, but also the way to spend the least money, can you help him?
In this mission, Mr. Frog is asked to pass a
dangerous region which is currently under his enemies, control. Every second he is inside this region, his enemies would attack him with everything they have. Luckily, he is wearing a powersuit and still have time to enhance it.
powersuit has three main attributes： health point, velocity and recover speed. In the begin¬ning of this mission, the powersuit has H health points, and is able to move at no faster than Vm/s. Once the health point of powersuit is less than 0, the powersuit would be totally destroyed and Mr. Frog would immediately be killed. At the end of every second that the powersuit still works, the suit would repair itself and recover R health points.
After precise calculation, Mr. Frog has found that, to go through this area, he needs to run at least D meters distance, and every second his enemies, attack would cause A health point loss. Note that attacks take place all the time while the recover only happens at the end of every second, so you can consider that, in every whole second, the powersuit first loses A health points and then recovers R health points at the end of it, if it still works at that moment.
Mr. Frog could enhance his powersuit at any time he wants during the mission. At the beginning all three attributes of his powersuit equals to 0. He needs to pay $G_1$ in order to increase H by 1, while $G_2$ to increase V by 1 and $G_3$ to increase R by 1. For any of these three values, he can only increase it by non-negative integer. For some well-known reasons, Mr. Frog does not want to finish the game too quickly, so you cannot increase the powersuit's speed to more than D m/s. Since you looks so clever, now Mr. Frog wants to know not only how he can finish this mission, but also the way to spend the least money, can you help him?
Input
The first line contains only one integer T, which indicates the number of test cases. For each test case，there are five integers $D,A,G_1,G_2,G_3$.
Output
For each test case，output one line “Case #x: Ans’’，where x is the case number (starting from 1) and Ans is the minimum cost required to finish the mission.
Sample Input
2 5 1 1 2 5 10 1 1 2 5
Sample Output
Case #1: 7 Case #2: 8
Hint
1 <= D,A <= 500000, 1 <= G1, G2, G3 <= 200