给定两种购买物品的方案：花费 c1元购买 n1 个物品，或者花费 c2c2 元购买 n2n2 个物品。
方案可以无限使用，询问购买 n个物品至少要多少元，若无法恰好购买到 n 个物品输出 failed
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
#define int long long
int n;
int gcd(int a,int b,int &x,int &y){
if (b == 0){
x=1; y=0; return a;
}
int t = gcd(b,a%b,y,x); y -= a/b*x;
return t;
}
signed main(){
int c1,c2,n1,n2;
while(cin>>n&&n){
int x,y;
cin>>c1>>n1>>c2>>n2;
int g=gcd(n1,n2,x,y);
if(n%g){
cout<<"failed\n";continue;
}
x=x*n/g ,y= y*n/g ;
int A=(int)ceil(-(double)x/(double)(n2/g)),
B=(int)floor((double)y/(double)(n1/g));
if(B<A){
cout<<"failed\n";continue;
}
if(c1*(x+A*n2/g) +c2*(y-A*n1/g)<
c1*(x+B*n2/g) +c2*(y-B*n1/g)){
cout<<(x+A*n2/g) << ' '<< (y-A*n1/g) <<endl;
}
else{
cout<<x+B*n2/g<<' '<<(y-B*n1/g)<<endl;
}
}
}