题意：给两种宝石，体积S1,S2，价值V1,V2，背包容量n，求最大收益。

#include<bits/stdc++.h>
#define s first
#define e second
#define rep(i,a,b) for(ll i=a;i<=b;i++)
#define rep2(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
using namespace std;
int main()
{
    int T,C=0; ll S,S1,V1,S2,V2,ans;
    scanf("%d",&T);
    while(T--){
        scanf("%lld%lld%lld%lld%lld",&S,&S1,&V1,&S2,&V2);
        printf("Case #%d: ",++C); ans=0;
        if(S1<=S2&&V1>=V2) ans=max(ans,(S/S1)*V1);
        if(S2<=S1&&V2>=V1) ans=max(ans,(S/S2)*V2);
        if(S1*S1>=S){
            rep(i,0,S/S1)
              ans=max(ans,V1*i+(S-S1*i)/S2*V2);
        }
        if(S2*S2>=S){
            rep(i,0,S/S2)
              ans=max(ans,V2*i+(S-S2*i)/S1*V1);
        }
        if(S1*S1<S&&S2*S2<S){
            rep(i,0,max(S1,S2)){
                if(S>=S1*i) ans=max(ans,V1*i+(S-S1*i)/S2*V2);
                if(S>=S2*i) ans=max(ans,V2*i+(S-S2*i)/S1*V1);
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}