Paper Cutting

Time limit1sMemory limit128 MB

Summary

For each test case, decide whether an A by B grid of C by D cards fits on an E by F sheet in some rotation, then report the minimum number of straight cuts needed to separate the cards.

Level: Hard8 of 10
Topics: Math, Greedy, Geometry, Implementation
Solved: No attempts yet

Problem

A print shop needs business cards. After the cards are printed on one large sheet of paper, they are separated with a special cutting machine. Because operating the machine is expensive, the number of cuts must be as small as possible. Your task is to find the optimal way to produce the cards.

Several rules apply. The cards are always printed as a grid of exactly $A \times B$ cards. The grid size (the number of cards in one row and in one column) is fixed and cannot be changed. The sheet is rectangular and its size is fixed as well. The grid must be aligned with the edges of the sheet; it may be rotated only by 90 degrees. You may swap the roles of rows and columns and place the grid anywhere on the sheet, and the cards may even touch the edges of the paper.

For example, suppose a card is $3 \times 4$ cm and the grid is $1 \times 2$ cards. The four possible orientations of the grid are shown below, each labelled with the smallest sheet that can hold it.

The cutting machine makes one straight cut of arbitrary length at a time. Each cut must run all the way through the piece of paper; it cannot stop in the middle. Only one loose piece of paper may be cut at a time — you may not stack pieces on top of one another, nor place them side by side, to save cuts.

Input

The input consists of several test cases. Each test case is given on one line as six positive integers $A$ , $B$ , $C$ , $D$ , $E$ , $F$ separated by spaces:

$A$ and $B$ are the dimensions of the card grid, with $1 \le A, B \le 1000$ ;
$C$ and $D$ are the dimensions of a single card in centimeters, with $1 \le C, D \le 1000$ ;
$E$ and $F$ are the dimensions of the paper sheet in centimeters, with $1 \le E, F \le 1000000$ .

The input ends with a line containing six zeros, which is not processed.

Output

For each test case, print a single line. If the grid of cards fits on the sheet, print

The minimum number of cuts is X.

where X is the minimum number of cuts required. Otherwise print

The paper is too small.

Examples3

Example 1

Input

1 2 3 4 9 4
1 2 3 4 8 3
1 2 3 4 5 5
3 3 3 3 10 10
0 0 0 0 0 0

Expected output

The minimum number of cuts is 2.
The minimum number of cuts is 1.
The paper is too small.
The minimum number of cuts is 10.

Example 2

Input

1 1 5 5 5 5
0 0 0 0 0 0

Expected output

The minimum number of cuts is 0.

Example 3

Input

1000 1000 1000 1000 1 1
0 0 0 0 0 0

Expected output

The paper is too small.