#include<bits/stdc++.h> using namespace std; const int N=100000; int T,m,n,d,f[N],w[N],v[N],lastn,maxn; int main(){ cin>>T; for(int t=1;t<=T;t++){ lastn=0,maxn=0; cin>>m>>n>>d; for(int i=1;i<=d;i++)cin>>w[i]>>v[i]; for(int i=1;i<=n;i++){ memset(f,0,sizeof(f)); for(int j=1;j<=d;j++){ for(int k=(lastn+w[j])/1000;k<=m/1000;++k){ f[k]=max(f[k-(w[j]/1000)]+v[j],f[k]); maxn=max(maxn,f[k]); } } // for(int j=1;j<=m/1000;j++)cout<<f[j]<<' '; //lastn=m; m+=maxn; //cout<<m<<endl; } cout<<m<<endl; } }