#include<bits/stdc++.h> using namespace std; int w[100097],v[100097],dp[100097],s,n,d; int main() { int t; cin>>t; while(t--) { cin>>s>>n>>d; for(int i=1; i<=d; ++i) { cin>>w[i]>>v[i]; } for(int i=1; i<=n; ++i) { int m=s/1000; for(int j=1; j<=d; ++j) { for(int k=w[j]/1000; k<=m; ++k) { if(k>=w[j]/1000) dp[k]=max(dp[k],dp[k-w[j]/1000]+v[j]); } } s+=dp[m]; memset(dp,0,sizeof(dp)); } cout<<s<<endl; } return 0; }