B - Pancakes

Time limit: 2 s
Memory limit: 128 MiB
Languages: C, C++, Java, JavaScript, ... (details)

A filled pancake consists of a pancake and its filling. In this problem, you will be given a list of ingredients you have and your task is to prepare as many filled pancakes as possible. Given 8 cups of milk, 8 egg yolks, 4 tablespoons of sugar, 1 teaspoon of salt, and 9 cups of flour, we can prepare 16 pancakes. For the purpose of this problem, we assume that these quantities scale arbitrarily:

for any x >= 0, if you have x times as much of every ingredient, you can prepare |_16x_| pancakes.

Given the necessary ingredients, you can prepare the following fillings:

-       banana pancake: 1 banana

-       strawberry pancake: 30 g of strawberry jam

-       chocolate pancake: 25 g of chocolate spread

-       walnut pancake: 10 walnuts

-       * banana pancake with chocolate: 3/4 of a banana, 10 g of chocolate spread

-       * walnut pancake with chocolate: 7 walnuts, 10 g of chocolate spread

-       * grand mix pancake: 1/3 of a banana, 3 walnuts, 5 g of strawberry jam, and 5 g of chocolate spread

Banana pieces can be combined. For example, you can use three pieces of 1/3 banana each to create

a banana pancake. For the easy subproblem, ignore the pancakes marked by a star .

Input

The first line of the input contains an integer t specifying the number of test cases. Each test case

is preceded by a blank line. Each test case consists of two lines.

The first  line of a test case contains five integers Cm , Y, Ssu, Ssa, and f, meaning that you have Cm cups of milk, Y egg yolks, Ssu tablespoons of sugar, Ssa teaspoons of salt, and f cups of flour. The second line contains four integers b,Gs, Gc, and w, meaning that you have b bananas, Gs grams of strawberry jam, Gc grams of chocolate spread, and w walnuts. All quantities are between 0 and 10 6 , inclusive.

Output

For each test case, output a single line containing a single integer( the maximum number of filled

pancakes you can prepare).

Sample test(s)

Input
2 16 16 8 2 17 10 47 100 19 16 16 8 2 17 10 470 100 19
Output
16 30

Hints

In the first test case, we are limited by the number of fillings: we can make 10 banana pancakes,

1 strawberry pancake, 4 chocolate pancakes, and 1 walnut pancake. In the second test case, we only

have enough our for 30 pancakes.

If we solved the same input in the hard subtask, the first answer would be 17: First, make 3 grand mix

pancakes. You are left with 9 bananas, 32 g of strawberry jam, 85 g of chocolate spread, and 10 walnuts.

That is enough for another 9+1+3+1=14 easy pancakes.