세탁소의 두 가지 운전권

문제

한 세탁소가 행사장에서 사용한 같은 종류의 천 W장을 오늘 안에 세탁하려 한다. 천은 모두 크기와 세탁 조건이 같으며, 어느 운전 방식에 넣어도 된다. 세탁소에는 가형과 나형이라는 두 가지 세탁 운전권이 있다. 운전권 한 장을 사용하면 해당 방식으로 세탁기를 한 번 운전할 수 있다. 가형 운전은 한 번에 최대 A장, 나형 운전은 한 번에 최대 B장의 천을 처리한다. 천 한 장을 여러 운전으로 나누어 처리할 수는 없지만, 각 운전에 넣는 천의 수는 정해진 최대 장수보다 적어도 된다. 오늘 사용할 수 있는 가형 운전권은 최대 X장이고 나형 운전권은 최대 Y장이다. 가형 운전권 한 장의 비용은 C이고 나형 운전권 한 장의 비용은 D다. 사용하지 않은 운전권의 비용은 계산하지 않으며, 운전 시간을 비롯한 다른 제한이나 비용은 없다. 가형 운전권을 x장, 나형 운전권을 y장 사용하는 계획은 0 ≤ x ≤ X, 0 ≤ y ≤ Y를 만족해야 한다. 또한 처리할 수 있는 최대 장수인 Ax + By가 W 이상이면 모든 천을 세탁할 수 있는 계획으로 인정한다. 담당자는 가능한 계획 중 총비용 Cx + Dy가 가장 작은 것을 고른다. 총비용이 같은 계획이 여러 개라면 사용한 운전권의 총 장수 x + y가 더 작은 것을 고른다. 총비용과 총 장수까지 모두 같다면 가형 운전권의 장수 x가 더 작은 것을 고른다. 남는 처리 용량의 크기는 계획을 고르는 기준에 포함하지 않는다. 두 종류의 운전권을 함께 사용해도 되고 한 종류만 사용해도 된다. 정해진 우선순위에 따라 선택한 계획과 그 비용을 출력한다. 모든 운전권을 사용해도 천을 전부 세탁할 수 없다면 -1을 출력한다.

입력

첫째 줄에 W, A, B가 공백으로 구분되어 주어진다. 둘째 줄에 X, Y, C, D가 공백으로 구분되어 주어진다. 모든 입력값은 정수이며 1 ≤ W ≤ 100,000, 1 ≤ A, B ≤ 100, 0 ≤ X, Y ≤ 300, 1 ≤ C, D ≤ 10,000이다.

출력

가능한 계획이 있으면 선택한 가형 운전권 장수 x, 나형 운전권 장수 y, 총비용을 공백으로 구분하여 한 줄에 출력한다. 가능한 계획이 없으면 -1만 출력한다.

11 3 5
3 2 4 7

2 1 15

8 4 4
2 2 5 5

0 2 10

10 2 3
1 2 4 6

-1

출처: Devin.KR 자체 제작