Problem Description
P. T. Tigris has been an avid computer game lover since he was a little boy fifteen years ago. “Age of Empires” was one of the most famous real-time strategy games in that past years. Resource is one of the most important consideration when playing this game. In this game, there are four different types of resources: food, wood, stone and gold.
Food is the most important resource in the game, which is used for producing many military units and researching important technologies. Wood is most often required for buildings or training ranged units. Stone is mainly used to build static defenses like Towers and Walls, but it is also used for some units and technologies as well as Wonders. Finally, gold is used for creating most units and upgrades and is a precious resource which becomes more important as the game progresses.
The Villager is a common civilian unit for almost every game. They are the backbone of all civilizations. The Villagers are arguably the most important units in the game because they are able to collect all the resources.
P. T. Tigris is very interesting in the optimal strategy of game playing. He wants to discover the fastest way to gather enough resources. We may assume that P. T. Tigris has N villagers at the beginning of the game with initially no food, wood, stone or gold at all. P. T. Tigris knows that every second, each villager could gather A1 units of food, or B1 units of wood, or C1 units of stone, or D1 units of gold. Note that the villager can not split one second into smaller pieces to gather different types of resource. For example, a single villager
can not gather A1/2 units of food and B1/2 units of wood for a single second. Moreover, all kinds of recourse are gathered exactly the end of that second.
Different villagers could gather different types of resources at a time. P. T. Tigris should decide which type of resources he should gather for each villager at every second, so that he could have A2 units of food and B2 units of wood and C2 units of stone and D2 units of gold as soon as possible.
P. T. Tigris could also training more villagers to speed up his process of gathering. To training a villager, P. T. Tigris should spend X units of food at the beginning of a second, and a new villager will able to work after T seconds. Please note that at he beginning of the second you start training a villager, you must have not less than X units of food. All villagers are trained at the Town Center but unfortunately there is only one Town Center for P. T. Tigris. So he can only train one villager at a time.
It is really difficult to find the optimal answer. P. T. Tigris decides to ask you to write a program to help him calculate the minimum time to get the required amount of resources.
Input
There are several test cases.
For each test case, the first line contains four integers A1, B1, C1 and D1 (1 ≤ A1, B1, C1, D1 ≤ 1018),indicating the amount of resource a villager can gather for each type in a second.
The second line also contains four integers A2, B2, C2 and D2 (0 ≤ A2, B2, C2, D2 ≤ 1018), denoting the amount of resource P. T. Tigris want to have.
The third line contains three integers N, X and T (1 ≤ N,X,T ≤ 105), denoting that P. T. Tigris has N villager at the beginning of the game, and it will spend X units of food and T seconds to train each new villager.
Input is terminated by EOF.
Output
For each test case, output one line “Case X: Y” where X is the test case number (starting from 1) and Y is an integer indicating the minimum time required to reach his goal.
Sample Input
1 1 1 1
1 1 1 1
4 1 1
1 1 1 1
2 2 2 2
1 1 1
1 1 1 1
10 10 10 10
1 1 25
Sample Output
Case 1: 1
Case 2: 5
Case 3: 34
