Internet Problem Solving Contest

IPSC 2011

Problem P – Pancakes!

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 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 specification

The first line of the input file 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 106, inclusive.

Output specification

For each test case, output a single line containing a single integer – the maximum number of filled pancakes you can prepare.

Example for the easy subtask


16 16 8 2 17
10 47 100 19

16 16 8 2 17
10 470 100 19

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 flour 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.