#include<bits/stdc++.h> using namespace std; int T,t,i,j,dp[1000000],w[1000000],p[1000000],d,k,a,s,n; int main() { cin>>T; for(s=1;s<=T;s++) { cin>>a>>n>>d; for(i=0;i<d;i++) { scanf("%d%d",&w[i],&p[i]); w[i]/=1000; } for(i=0;i<n;i++) { t=a/1000; for(j=0;j<d;j++) for(k=w[j];k<=t;k++) dp[k]=max(dp[k],dp[k-w[j]]+p[j]); a+=dp[t]; } printf("%d\n",a); } return 0; }