卡常

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
ll t,n,s1,s2,v1,v2,cas,s,mx;
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>t;
	while(t--){
		s=0,mx=0;
		cin>>n>>s1>>v1>>s2>>v2;
		s+=n/s1/s2*max(s1*v2,s2*v1);
		n%=s1*s2;
		if(s1<s2) swap(s1,s2),swap(v1,v2);
		for(ll i=0;i<=n/s2;i++){
			if(i*v2+(n-s2*i)/s1*v1>mx){
				mx=i*v2+(n-s2*i)/s1*v1;
			}
		}s+=mx;
		cout<<"Case #"<<++cas<<": "<<s<<endl;
	}
	return 0;
}