eolymp
bolt
Try our new interface for solving problems
Problems

Marbles

Marbles

Time limit 1 second
Memory limit 64 MiB

I have some (say, n) marbles (small glass balls) and I am going to buy some boxes to store them. The boxes are of two types:

Type1: each box costs c_1 Taka and can hold exactly n_1 marbles

Type2: each box costs c_2 Taka and can hold exactly n_2 marbles

I want each of the used boxes to be filled to its capacity and also to minimize the total cost of buying them. Since I find it difficult for me to figure out how to distribute my marbles among the boxes, I seek your help. I want your program to be efficient also.

Input data

The input file may contain multiple test cases. Each test case begins with a line containing the integer n (1n2000000000). The second line contains c_1 and n_1, and the third line contains c_2 and n_2. Here, c_1, c_2, n_1 and n_2 are all positive integers having values smaller than 2000000000.

A test case containing a zero for n in the first line terminates the input.

Output data

For each test case in the input print a line containing the minimum cost solution (two nonnegative integers m_1 and m_2, where m_i = number of Type i boxes required) if one exists, print "failed" otherwise.

If a solution exists, you may assume that it is unique.

Examples

Input example #1
43
1 3
2 4
40
5 9
5 12
0
Output example #1
13 1
failed