우편 실습용 우표 꾸러미

문제

한 우체국에서는 새 직원의 계산 실습에 사용할 우표 꾸러미를 만들고 있다. 실습대에는 세 종류의 우표가 놓여 있으며, 종류에는 각각 1번, 2번, 3번이라는 번호가 붙어 있다. 각 종류의 우표는 정해진 금액을 나타내고, 실습대에 놓인 수량만큼만 사용할 수 있다. 같은 종류의 우표끼리는 서로 구별하지 않는다. 이번 실습의 기준 금액은 B이다. 직원은 세 종류의 우표 중 일부를 골라 꾸러미 하나를 만든다. 꾸러미에는 우표가 적어도 한 장 들어가야 하며, 우표 금액의 합은 B를 넘을 수 없다. 기준 금액을 정확히 맞추지 못해도 꾸러미를 만들 수 있다. 사용하지 않은 우표는 실습대에 남겨 두며, 남은 수량은 평가에 영향을 주지 않는다. 꾸러미를 고르는 기준에는 순서가 있다. 먼저 금액의 합이 가장 큰 꾸러미를 고른다. 금액의 합이 같은 꾸러미가 여러 개라면 사용한 우표의 총 장수가 가장 적은 것을 고른다. 금액의 합과 총 장수까지 같다면 1번 우표를 적게 사용한 것을 고르고, 그 수까지 같다면 2번 우표를 적게 사용한 것을 고른다. 이 조건들까지 같으면 3번 우표의 수도 같으므로 결과가 하나로 정해진다. 우표의 종류는 금액이 아니라 번호로 구별한다. 따라서 서로 다른 종류의 우표가 같은 금액을 나타낼 수도 있다. 어떤 종류의 재고가 0장인 입력도 주어진다. 우표를 잘라 사용하거나 다른 금액의 우표로 교환할 수는 없으며, 실습대에 없는 우표를 새로 가져올 수도 없다. 모든 금액은 양의 정수이다. 정해진 기준에 따라 꾸러미의 금액 합과 각 종류의 사용 수량을 구한다. 한 장 이상의 우표로 기준 금액 이하의 꾸러미를 만들 수 없다면 -1을 출력한다. 빈 꾸러미는 금액의 합이 0이더라도 답으로 인정하지 않는다. 이번 문제의 기준 금액은 실제 우편 요금이 아니라 실습을 위해 주어진 숫자이다.

입력

첫째 줄에 기준 금액 B가 주어진다. 1≤B≤600,000이다.
둘째 줄에 1번, 2번, 3번 우표의 금액 A₁, A₂, A₃이 주어진다. 1≤Aᵢ≤1,000이다.
셋째 줄에 각 종류의 재고 C₁, C₂, C₃이 주어진다. 0≤Cᵢ≤200이다. 모든 입력값은 정수이다.

출력

가능한 꾸러미가 없다면 -1을 한 줄에 출력한다. 그렇지 않으면 선택한 꾸러미의 금액 합과 1번, 2번, 3번 우표의 사용 수량을 이 순서대로 한 줄에 공백으로 구분하여 출력한다.

17
4 7 9
3 2 1

17 2 0 1

12
4 4 6
3 3 2

12 0 0 2

3
4 5 8
2 0 1

-1

출처: Devin.KR 자체 제작