창구의 교환 봉투

문제

어느 은행 창구에서는 미리 준비한 현금 봉투를 고객에게 건네는 방식으로 금액을 교환한다. 봉투는 세 종류이며, 각 종류의 봉투에는 각각 a원, b원, c원이 들어 있다. 세 금액은 a < b < c를 만족한다. 같은 종류의 봉투에는 항상 같은 금액이 들어 있고, 창구에는 각 종류가 각각 A개, B개, C개 준비되어 있다. 고객은 정확히 T원을 받아 가려고 한다. 창구 직원은 준비된 봉투 중 일부를 골라 고객에게 건네야 한다. 봉투를 뜯어 돈을 나누거나, 다른 종류의 봉투로 바꾸어 준비하거나, 창구에 없는 봉투를 추가할 수는 없다. 한 종류의 봉투를 전혀 사용하지 않는 것은 가능하다. 선택한 봉투에 들어 있는 금액의 합은 반드시 T원과 정확히 같아야 하며, 초과한 금액을 고객이 돌려주는 방식은 허용하지 않는다. 조건을 만족하는 선택이 여러 개라면 직원은 건네는 봉투의 총개수가 가장 적은 선택을 사용한다. 총개수까지 같다면 c원 봉투를 더 많이 사용하는 선택을 고른다. c원 봉투의 개수도 같다면 b원 봉투를 더 많이 사용하는 선택을 고른다. 세 종류의 사용 개수가 모두 같으면 같은 선택으로 취급한다. 이 기준을 적용하면 출력할 선택은 하나로 정해진다. 고객이 요청한 금액이 0원일 수도 있다. 이때는 봉투를 하나도 건네지 않는 선택이 가능하며, 총개수가 가장 적으므로 그 선택을 사용한다. 반대로 준비된 봉투를 어떻게 골라도 요청 금액을 만들 수 없다면 교환이 불가능하다고 보고해야 한다. 봉투의 금액, 준비된 개수, 요청 금액이 주어질 때 위 기준에 따라 사용할 각 종류의 봉투 개수를 구하는 프로그램을 작성한다.

입력

첫째 줄에 정수 a, b, c가 주어진다. 1 ≤ a < b < c ≤ 10,000이다.
둘째 줄에 정수 A, B, C가 주어진다. 각각 0 이상 100 이하이다.
셋째 줄에 정수 T가 주어진다. 0 ≤ T ≤ 3,000,000이다.

출력

교환이 가능하면 사용할 a원 봉투, b원 봉투, c원 봉투의 개수를 이 순서대로 공백으로 구분하여 한 줄에 출력한다. 교환이 불가능하면 -1을 출력한다.

2 4 6
3 3 3
8

1 0 1

3 7 11
2 1 0
5

-1

1 5 9
0 0 0
0

0 0 0

출처: Devin.KR 자체 제작