## Algorithm

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: T ype 1: each box costs c1 Taka and can hold exactly n1 marbles T ype 2: each box costs c2 Taka and can hold exactly n2 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 The input file may contain multiple test cases. Each test case begins with a line containing the integer n (1 ≤ n ≤ 2, 000, 000, 000). The second line contains c1 and n1, and the third line contains c2 and n2. Here, c1, c2, n1 and n2 are all positive integers having values smaller than 2,000,000,000. A test case containing a zero for n in the first line terminates the input. Output For each test case in the input print a line containing the minimum cost solution (two nonnegative integers m1 and m2, where mi = number of T ypei boxes required) if one exists, print ‘failed’ otherwise. If a solution exists, you may assume that it is unique.

Sample Input 43 1 3 2 4 40 5 9 5 12 0

Sample Output 13 1 failed

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

`````` #include <bits/stdc++.h>
using namespace std;
#define ll long long

ll x, y, d;
void extendedEuclid(ll a, ll b) {
if(b==0) { x=1; y=0; d=a; return;}
extendedEuclid(b, a%b);
ll y1 = x-(a/b)*y;
x = y;
y = y1;
}

int main() {
ll v,n1,n2,c1,c2;
while(scanf("%lld",&v),v){
scanf("%lld %lld %lld %lld",&c1,&n1,&c2,&n2);
extendedEuclid(n1,n2);
if (v%d != 0) {
printf("failed\n");
} else {
// to get to ax + by = v
x *= v/d;
y *= v/d;
// two equations of Linear Diophantine
/* x = x0 + (b/d)n, y = y0 − (a/d)n, where n is an integer */

// derivation of n based on the fact that x and y has to be positive
// x0 + (b/d)n >= 0, solve for n: we get n >= -x0*d/b
// y0 - (a/d)n >= 0, solve for n: we get n <= y0*a/b
// putting together x0*d/b  < = n <= y0*d/b
n2 /= d, n1 /= d; // divide first to prevent overflow
ll lowerbound=ceil(-(double)x/n2);
ll upperbound=floor((double)y/n1);
if(lowerbound < =upperbound) {
// compare cost
ll res1 = c1*(x+n2*lowerbound) + c2*(y-n1*lowerbound);
ll res2 = c1*(x+n2*upperbound) + c2*(y-n1*upperbound);
if (res1  <  res2) {
printf("%lld %lld\n",(x+n2*lowerbound), (y-n1*lowerbound));
} else {
printf("%lld %lld\n",(x+n2*upperbound), (y-n1*upperbound));
}
} else
printf("failed\n">;
}
}
}         ``````
Copy The Code &

Input

cmd
43
1 3
2 4
40
5 9
5 12
0

Output

cmd
13 1
failed