#include <bits/stdc++.h> using namespace std; int a,b,c,d,e,f,g[114514],h[114514],i,j,k[114514],l[114514]; int main() { cin>>a; for(b=1;b<=a;b++) { memset(k,0,sizeof(k)); cin>>c>>e>>d; for(f=0;f<d;f++) { cin>>g[f]>>h[f]; g[f]/=1000; } for(f=0;f<e;f++) { int t=c/1000; for(i=0;i<d;i++) for(j=g[i];j<=t;j++) k[j]=max(k[j],k[j-g[i]]+h[i]); c+=k[t]; } l[b]=c; } for(b=1;b<=a;b++) cout<<l[b]<<endl; return 0; }