창구 안내권 묶음 주문

문제

은행 창구에서는 방문객에게 업무 순서와 준비물을 적은 종이 안내권을 나누어 준다. 다음 영업일에 사용할 안내권을 주문하려고 하며, 필요한 안내권은 N장이다. 안내권은 낱장으로 주문할 수 없고 두 종류의 묶음으로만 주문할 수 있다. 첫 번째 종류는 한 묶음에 A장이 들어 있고 가격은 C원이며, 두 번째 종류는 한 묶음에 B장이 들어 있고 가격은 D원이다. 각 종류의 묶음은 원하는 만큼 주문할 수 있다. 첫 번째 종류를 x묶음, 두 번째 종류를 y묶음 주문하면 안내권은 모두 Ax + By장이 되고 주문 금액은 Cx + Dy원이 된다. x와 y는 각각 0 이상의 정수다. 필요한 수량보다 많이 주문해도 되지만, 주문한 안내권의 총수가 N장보다 적으면 사용할 수 없는 주문이다. 남은 안내권을 되팔거나 주문 금액에서 공제하는 일은 없다. 창구 담당자는 먼저 주문 금액이 가장 작은 주문을 선택한다. 주문 금액이 같은 주문이 여러 개라면 안내권의 총수가 가장 작은 주문을 선택한다. 금액과 안내권 총수가 모두 같다면 첫 번째 종류의 묶음 수 x가 가장 작은 주문을 선택한다. 두 종류의 묶음 구성이 같더라도 주문서에서는 서로 다른 종류로 구분하므로 이 마지막 기준도 그대로 적용한다. 두 종류 모두 재고가 충분하고 모든 가격이 양수이므로 조건을 만족하는 주문은 항상 존재한다. 또한 위의 선택 기준을 차례대로 적용하면 주문할 묶음 수가 하나로 정해진다. 담당자가 선택할 첫 번째 종류의 묶음 수, 두 번째 종류의 묶음 수, 그리고 그 주문의 총금액을 구한다. 묶음의 가격이나 한 장당 가격이 작은 종류를 먼저 고르는 방식이 항상 가장 좋은 주문을 보장하는 것은 아니다.

입력

첫째 줄에 N이 주어진다. N은 1 이상 100,000 이하의 정수다.
둘째 줄에 A와 C가, 셋째 줄에 B와 D가 각각 공백으로 구분되어 주어진다. A와 B는 각각 1 이상 100,000 이하의 정수이고, C와 D는 각각 1 이상 10,000 이하의 정수다.

출력

선택한 주문의 x, y, 총금액을 공백으로 구분하여 한 줄에 출력한다.

17
6 5
4 4

3 0 15

12
6 6
4 4

0 3 12

7
4 4
3 4

1 1 8

출처: Devin.KR 자체 제작