Zoo Design

Problem Description

Aman is a rich businessman who want to build a zoo. He wants to make enclosures for terrestrial and aquatic animals. Terrestrial animals will be of two types, namely herbivorous and carnivorous animals. So there will be three different enclosures.
Herbivores like Elephant, Deer are prime attractions. Similarly, Lion and Tiger are prime attractions amongst carnivores. Finally, Dolphins and Shark are prime attractions amongst aquatics for tourists.
Aman being a savvy businessman realizes that in order to minimize the cost of building the zoo without compromising on the attractions, he has to decide how much area to allocate to each animal type. Each animal type requires a certain area to thrive in. This in turn impacts the area allocation, which in turn has cost implications.
Your task is to help Aman workout the mathematics such that the zoo building cost is minimized subject to the following constraints:
Zoo needs to have minimum of X herbivores, Y carnivores and Z aquatic animals
Different types of animals will need different minimum area to thrive in
For animals of a given type, the minimum area required is the same
There is also a maximum limit for the overall area allocated for each animal type
Cost of fencing etc. is included in cost of enclosure
Exclude the essentials like pathways for tourists, from area and cost calculations
Consider all areas in square meters and cost in Rupees.

Constraints

0 < number of animals of each type <= 20
0 < max area for each animal type <= 500
0 < total area of land on which zoo is to be built <= 1000
0 < min area required by individual animals <= 15
0 < price of each type of enclosure <= 10000
Area of each type of enclosure should be rounded off to the nearest integer

Input

First line contains three space separated integers denoting the cost per square meter of building the enclosure for each type of animals viz. herbivorous, carnivorous and aquatic respectively.

Second line contains three space separated integers denoting the maximum area that can be allocated to each type of animal viz. herbivorous, carnivorous and aquatic respectively

Next three lines, each will contain two space separated integers M and N, for each type of animal viz. herbivorous, carnivorous and aquatic respectively, where M denotes minimum number of animals of that type and N denotes minimum area required for that animal type

Last line contains an integer which represents the total area of land on which the zoo needs to be built

Output

Single integer containing the minimum cost required to build the zoo

Time Limit

1
Examples
Example 1
Input
10000 1000 1500
250 250 300
5 5
15 5
10 10
500
Output
837500
Explanation
·The cost of constructing the enclosure for herbivores is high. However, since we need to accommodate 5 herbivores as per given constraints, a 25 sq. meter land will need to allocated for the herbivores.
·Since the cost of constructing the enclosure for carnivores is cheapest we are able to allocate them the maximum limit that we can allocate. Thus we are allocating 250 sq. meters for carnivores.
·The remaining 225 sq. meters can thus be allocated to aquatics without violating any constraint.
·Thus the minimum cost of constructing the zoo adhering to all constraints is (25 * 10000 + 250 * 1000 + 225 * 1500) = 837500

Example 2
Input
100 1000 1500
250 250 300
5 5
15 5
10 10
500
Output
325000
Explanation
·Since the cost of constructing the enclosure for herbivores is cheapest we are able to allocate them the maximum limit that we can allocate. Thus we are allocating 250 sq. meters for herbivores.
·The cost of constructing the enclosure for aquatics is high. However, since we need to accommodate 10 aquatics as per given constraints, a 100 sq. meter land will need to allocated for the aquatic animals.
·The remaining 150 sq. meters can thus be allocated to carnivores without violating any constraint.
·Thus the minimum cost of constructing the zoo adhering to all constraints is (250 * 100 + 150 * 1000 + 100 * 1500) = 325000