Marbles#2298
I have marbles (small glass balls), and I want to buy some boxes to store them. The boxes come in two types:
Type : each box costs c_1 and holds exactly n_1 marbles.
Type : each box costs c_2 and holds exactly n_2 marbles.
I want every used box to be filled to its capacity, and I want to minimize the total cost of buying the boxes. Since I find it difficult to figure out how to distribute my marbles among the boxes, I seek your help. I also want your program to be efficient.
The input file may contain multiple test cases. Each test case begins with a line that contains one integer (1 \leq n \leq 2000000000). The second line contains c_1 and n_1; the third line contains c_2 and n_2. Here, c_1, c_2, n_1, and n_2 are positive integers less than .
A test case containing n = 0 in the first line terminates the input.
For each test case, print one line with the minimum cost solution: two nonnegative integers m_1 and m_2, where m_i is the number of boxes of type , if a solution exists; otherwise, print failed.
If a solution exists, it can be assumed to be unique.
Example 1