#include<bits/stdc++.h> using namespace std; #define int long long const int N=3e4+10; int id,T,m,a,b,c,d; int f[N],pw[N],fac[N],v[N],w[N]; signed main(){ // freopen("powerer.in","r",stdin); // freopen("powerer.out","w",stdout); fac[0]=pw[0]=1; for(int i=1;i<=15;i++){fac[i]=fac[i-1]*i;} for(int i=1;i<=40;i++){pw[i]=pw[i-1]*2;} scanf("%lld%lld",&id,&T); while(T--){ // cout<<"!"<<T<<endl; scanf("%lld%lld%lld%lld%lld",&m,&a,&b,&c,&d); int k=1; for(int i=1;fac[i]<=m;i++,k++){ w[i]=fac[i];v[i]=a+b*i; } for(int i=0;pw[i]<=m;i++,k++){ w[k]=pw[i];v[k]=c+d*i; }k--; // cout<<"-----------------------------"<<k<<endl; memset(f,0x7f,sizeof(f));f[0]=0; for(int i=1;i<=k;i++){ for(int j=m;j>=w[i];j--){ // cout<<i<<" "<<j<<endl; f[j]=min(f[j],f[j-w[i]]+v[i]); } } printf("%lld\n",f[m]); } // fclose(stdin);fclose(stdout); return 0; }