Question 5: 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.  

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.

Examples

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

TCS Codevita Pre-qualifier Round which was held on 15th August 2020 by TCS to filter out the candidates that suits  there company as  Software Engineers. The level of this Coding Round was medium and not that easy. Every candidate has to solve atleast one question to be qualified for the next round. The coding round comprised of good set of questions which are as follows :