종이 자르기

어느 인쇄소에서 명함을 만들려고 합니다. 명함은 큰 종이 한 장에 인쇄된 뒤 특수한 재단기로 잘라 냅니다. 재단기를 작동하는 비용이 비싸기 때문에 자르는 횟수를 최소로 줄여야 합니다. 명함을 만드는 최적의 방법을 찾으세요.

지켜야 하는 규칙이 있습니다. 명함은 항상 정확히 $A \times B$ 장의 격자 모양으로 인쇄됩니다. 격자의 크기(한 행과 한 열에 들어가는 명함 수)는 고정되어 있어 바꿀 수 없습니다. 종이는 직사각형이고 크기도 고정되어 있습니다. 격자는 종이의 변과 나란해야 하며, 90도 회전만 허용됩니다. 행과 열의 역할을 서로 바꿀 수 있고 격자를 종이 위 어디에나 놓을 수 있으며, 명함이 종이의 가장자리에 닿아도 됩니다.

예를 들어 명함의 크기가 $3 \times 4$ cm이고 격자가 $1 \times 2$ 장이라고 합시다. 격자를 놓을 수 있는 네 가지 방향이 아래 그림에 나와 있으며, 각 경우에 필요한 가장 작은 종이 크기가 함께 표시되어 있습니다.

재단기는 한 번에 임의의 길이의 직선을 한 번 자릅니다. 각 절단은 종이를 완전히 관통해야 하며 중간에서 멈출 수 없습니다. 한 번에 오직 한 장의 종이 조각만 자를 수 있습니다. 즉, 종이 조각을 서로 겹쳐 쌓거나 나란히 붙여 놓아 절단 횟수를 줄일 수는 없습니다.

입력은 여러 개의 테스트 케이스로 이루어집니다. 각 테스트 케이스는 한 줄에 공백으로 구분된 여섯 개의 양의 정수 $A$, $B$, $C$, $D$, $E$, $F$로 주어집니다.

• $A$와 $B$는 명함 격자의 크기이며 $1 \le A, B \le 1000$입니다.
• $C$와 $D$는 명함 한 장의 크기(cm)이며 $1 \le C, D \le 1000$입니다.
• $E$와 $F$는 종이 한 장의 크기(cm)이며 $1 \le E, F \le 1000000$입니다.

입력은 여섯 개의 0으로 이루어진 줄로 끝나며, 이 줄은 처리하지 않습니다.

각 테스트 케이스마다 한 줄을 출력합니다. 명함 격자를 종이에 놓을 수 있으면

The minimum number of cuts is X.

를 출력하며, 여기서 X는 필요한 최소 절단 횟수입니다. 놓을 수 없으면 대신

The paper is too small.

를 출력합니다.