#include<bits/stdc++.h> #define int long long #define pii pair<int,int> #define mkp make_pair using namespace std; void init(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); //freopen("powerer.in","r",stdin);freopen("powerer.out","w",stdout); //freopen("test.in","r",stdin);freopen("test.out","w",stdout); } pii num[(1<<14)+100]; int sum[(1<<14)+100]; int jx[20]; signed main(){ init(); int id,t; cin>>id>>t; jx[1]=1; for(int i=2;i<=15;i++){jx[i]=jx[i-1]*i;} num[0]=mkp(0,0); sum[0]=0; for(int i=1;i<(1<<14);i++){ int lb; for(int j=14;j>=0;j--){ if((i>>j)&1==1){lb=j;break;} } num[i]=mkp(num[i-(1<<lb)].first+1,num[i-(1<<lb)].second+lb+1); sum[i]=sum[i-(1<<lb)]+jx[lb+1]; } while(t--){ int ans=0x7f7f7f7f7f7f7f7f; int m,a1,a2,b1,b2; cin>>m>>a1>>b1>>a2>>b2; for(int i=0;i<(1ll<<14ll);i++){ if(sum[i]<=m){ int s=sum[i],cost=num[i].first*a1+num[i].second*b1; for(int j=0;j<60;j++){ if(j==1&&((i>>1)&1)==1){ if(((s>>j)&1ll)!=((m>>j)&1ll)){ s=0; break; }else{ cost-=(a1+b1*2ll); cost+=min(a1+b1*2ll,a2+b2*1ll); } }else if(j==0&&((i>>0)&1)==1){ if(((s>>j)&1ll)!=((m>>j)&1ll)){ s=0; break; }else{ cost-=(a1+b1*1ll); cost+=min(a1+b1*1ll,a2+b2*0ll); } }else{ if(((s>>j)&1)!=((m>>j)&1)){ s+=((1ll)<<j); cost+=a2+b2*j; } } } //cout<<s<<' '<<i<<' '<<cost<<' '<<num[i].first*a1+num[i].second*b1<<' '<<sum[i]<<endl; if(s==m)ans=min(ans,cost); } } cout<<ans<<endl; } }