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