호텔의 수건 꾸러미

문제

한 호텔은 단체 손님에게 나누어 줄 새 수건을 준비하고 있다. 필요한 수건은 모두 N장이며, 창고에 남아 있는 수건은 없다. 납품 담당자는 수건을 낱장으로 판매하지 않고 두 종류의 꾸러미로만 판매한다. 첫 번째 꾸러미에는 수건 A장이 들어 있고 가격은 P원이다. 두 번째 꾸러미에는 수건 B장이 들어 있고 가격은 Q원이다. 각 종류는 필요한 만큼 제한 없이 구입할 수 있다. 호텔은 구입한 수건의 총수가 N장 이상이 되도록 꾸러미를 주문해야 한다. 필요한 수량보다 많은 수건을 구입해도 되며, 남은 수건은 창고에 보관한다. 꾸러미를 나누어 주문하거나 일부 수건만 반품할 수는 없다. 첫 번째 꾸러미를 x개, 두 번째 꾸러미를 y개 주문하면 수건은 Ax+By장이고 지출 금액은 Px+Qy원이다. x와 y는 각각 0 이상의 정수이며, 한 종류만 구입하는 것도 허용된다. 주문 방법은 다음 우선순위에 따라 결정한다. 먼저 지출 금액이 가장 작은 방법을 선택한다. 지출 금액이 같다면 필요한 수량을 초과하여 남는 수건 수가 가장 작은 방법을 선택한다. 금액과 남는 수건 수까지 같다면 첫 번째 꾸러미의 개수 x가 가장 작은 방법을 선택한다. 꾸러미 종류의 입력 순서는 이 마지막 동점 규칙에서 의미를 가지므로 임의로 바꾸어서는 안 된다. 모든 꾸러미의 가격은 양수다. 따라서 특정 종류만으로 필요한 수량을 이미 채웠는데 같은 종류를 더 구입하는 것은 더 좋은 주문이 될 수 없다. 또한 첫 번째 꾸러미의 개수를 정했다면, 부족한 수건을 채우는 데 필요한 최소 개수의 두 번째 꾸러미만 고려하면 된다. 이 성질을 이용해 가능한 주문을 빠짐없이 비교할 수 있다. 호텔이 선택할 주문의 총금액과 두 종류의 꾸러미 개수를 구한다. 두 종류 모두 공급량 제한이 없으므로 조건을 만족하는 주문은 항상 존재한다. 수건이 정확히 N장인 주문이 없더라도 위 우선순위를 그대로 적용한다.

입력

첫째 줄에 필요한 수건 수 N이 주어진다. N은 1 이상 100,000 이하의 정수다.
둘째 줄에 첫 번째 꾸러미의 수건 수 A와 가격 P가 주어진다.
셋째 줄에 두 번째 꾸러미의 수건 수 B와 가격 Q가 주어진다.
A와 B는 1 이상 100,000 이하의 정수이며, P와 Q는 1 이상 1,000,000 이하의 정수다. 같은 종류의 꾸러미 개수에는 제한이 없다.

출력

선택한 주문의 총금액, 첫 번째 꾸러미 개수 x, 두 번째 꾸러미 개수 y를 공백으로 구분하여 한 줄에 출력한다.

13
5 7
8 10

17 1 1

10
6 5
5 5

10 0 2

12
4 3
6 6

9 3 0

출처: Devin.KR 자체 제작