간식 꾸러미 발주

문제

편의점에서는 동네 행사에 보낼 간식을 두 종류의 꾸러미로 발주한다. 첫 번째 꾸러미에는 간식 A개가 들어 있고 가격은 P원이다. 두 번째 꾸러미에는 같은 간식 B개가 들어 있고 가격은 Q원이다. 꾸러미에 들어 있는 간식은 모두 동일하므로 행사 담당자는 꾸러미 종류에 관계없이 간식의 전체 개수만 확인한다. 편의점은 남는 간식을 보관할 공간이 없어 주문받은 D개를 정확히 맞추어야 한다. 공급 창고는 이번 발주에서 첫 번째 꾸러미와 두 번째 꾸러미를 각각 최대 100개까지 제공한다. 따라서 첫 번째 꾸러미를 a개, 두 번째 꾸러미를 b개 발주한다면 a와 b는 각각 0 이상 100 이하의 정수여야 한다. 어느 한 종류를 전혀 발주하지 않아도 된다. 꾸러미를 뜯어 일부만 구입하거나 다른 종류의 상품을 추가로 구입할 수는 없다. 간식 수가 D개보다 많거나 적은 발주는 모두 허용되지 않는다. 정확한 개수를 맞출 수 있는 발주 방법이 여러 개라면 총가격이 가장 작은 방법을 선택한다. 총가격도 같다면 운반 상자 수를 줄이기 위해 꾸러미 개수의 합 a+b가 가장 작은 방법을 선택한다. 총가격과 꾸러미 개수의 합이 모두 같다면 첫 번째 꾸러미 개수 a가 가장 작은 방법을 선택한다. 이 규칙을 순서대로 적용하면 선택할 발주 방법은 하나로 결정된다. 배송비나 할인은 없으며 총가격은 aP+bQ원이다. 두 종류의 구성과 가격, 필요한 간식 수가 주어졌을 때 선택할 발주 방법을 구하는 프로그램을 작성한다. 창고의 수량 제한 때문에 정확한 개수를 만들 수 없는 경우에는 그 사실을 출력한다. A와 B가 같거나 P와 Q가 같은 입력도 주어질 수 있으며, 이때에도 같은 선택 규칙을 적용한다.

입력

첫째 줄에 정수 A, P, B, Q, D가 공백으로 구분되어 주어진다.
1 ≤ A, B ≤ 100이며 1 ≤ P, Q ≤ 10,000이다. 필요한 간식 수 D는 1 이상 20,000 이하의 정수이다.
각 종류의 꾸러미는 0개 이상 100개 이하로 발주할 수 있다.

출력

가능한 발주 방법이 있으면 선택된 첫 번째 꾸러미 개수 a와 두 번째 꾸러미 개수 b를 공백으로 구분하여 출력한다. 정확히 D개를 만들 수 없으면 -1만 출력한다.

4 7 6 10 24

0 4

4 8 6 12 7

-1

5 9 5 9 15

0 3

출처: Devin.KR 자체 제작