출고 묶음을 위한 칸막이

문제

물류 창고에 가로 길이가 W, 세로 길이가 H인 직사각형 적재장이 있다. 담당자는 가로 방향의 정수 위치 X에 두께가 없는 칸막이를 세워 적재장을 두 구역으로 나누려 한다. 왼쪽 구역의 가로 길이는 X이고 오른쪽 구역의 가로 길이는 W-X다. X는 0부터 W까지의 정수이며, 양 끝에 칸막이를 세워 한쪽 구역의 가로 길이가 0이 되는 것도 허용한다. 왼쪽 구역에는 A형 상자만 놓고 오른쪽 구역에는 B형 상자만 놓는다. A형 상자의 바닥은 가로 a, 세로 b인 직사각형이고, B형 상자의 바닥은 가로 c, 세로 d인 직사각형이다. 모든 길이는 같은 단위를 사용한다. 상자를 회전하거나 쌓을 수 없으며, 상자가 구역 밖으로 나가거나 서로 겹치게 놓을 수도 없다. 창고에서는 각 구역의 왼쪽 아래 모서리부터 상자를 가로와 세로 방향으로 빈틈없이 정렬하는 격자 배치만 사용한다. 따라서 왼쪽 구역에 놓을 수 있는 A형 상자의 최대 개수는 floor(X/a) × floor(H/b)이고, 오른쪽 구역에 놓을 수 있는 B형 상자의 최대 개수는 floor((W-X)/c) × floor(H/d)다. 여기서 floor는 나눗셈 결과의 소수 부분을 버리는 연산이다. 남는 공간은 비워 두며 다른 종류의 상자로 채우지 않는다. 출고 묶음 하나를 만들려면 A형 상자 P개와 B형 상자 Q개가 필요하다. 상자는 종류별로 충분히 준비되어 있고, 구역에 놓은 상자만 묶음에 사용할 수 있다. 한 상자를 여러 묶음에 중복해서 사용할 수 없으며, 묶음을 만들고 남은 상자는 사용하지 않아도 된다. 만들 수 있는 출고 묶음 수가 최대가 되도록 칸막이 위치를 정한다. 최대 묶음 수가 같은 위치가 여러 개라면 X가 가장 작은 위치를 선택한다. 어떤 위치에서도 묶음을 하나도 만들 수 없다면 최대 묶음 수는 0으로 보고 위치 대신 -1을 출력한다. 모든 길이와 묶음에 필요한 상자 수는 양의 정수다.

입력

첫째 줄에 적재장의 가로와 세로 길이 W, H가 주어진다. 둘째 줄에 A형 상자의 가로와 세로 길이 a, b가 주어진다. 셋째 줄에 B형 상자의 가로와 세로 길이 c, d가 주어진다. 넷째 줄에 출고 묶음 하나에 필요한 상자 수 P, Q가 주어진다. 모든 값은 정수이며 각각 1 이상 100,000 이하이다. 상자의 한 변이 적재장의 해당 방향 길이보다 클 수도 있다.

출력

최대 출고 묶음 수와 선택한 칸막이 위치 X를 공백으로 구분하여 출력한다. 묶음을 하나도 만들 수 없으면 0 -1을 출력한다.

11 6
2 3
3 2
2 3

2 4

5 4
2 2
2 2
1 1

2 2

8 3
2 4
1 1
1 1

0 -1

출처: Devin.KR 자체 제작