Age of Empires

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 A₁ units of food, or B₁ units of wood, or C₁ units of stone, or D₁ 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 A₁/2 units of food and B₁/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 A₂ units of food and B₂ units of wood and C₂ units of stone and D₂ 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.

There are several test cases.
For each test case, the first line contains four integers A₁, B₁, C₁ and D₁ (1 ≤ A₁, B₁, C₁, D₁ ≤ 10¹⁸),indicating the amount of resource a villager can gather for each type in a second.
The second line also contains four integers A₂, B₂, C₂ and D₂ (0 ≤ A₂, B₂, C₂, D₂ ≤ 10¹⁸), 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 ≤ 10⁵), 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.

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.

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

Case 1: 1
Case 2: 5
Case 3: 34

2012 Asia Chengdu Regional Contest