#include<bits/stdc++.h> using namespace std; int weight[10000],profit[10000]; int n,amount; int work(int d){ int dp[100005]={0}; dp[0]=0; for(int i=0;i<d;i++){ cin>>weight[i]>>profit[i]; weight[i] /= 1000; } for(int i=0;i<n;i++){ int t = amount / 1000; for(int j=0;j<d;j++){ for(int k=weight[j];k<=t;k++){ dp[k] = max(dp[k],dp[k-weight[j]]+profit[j]); } } amount += dp[t]; } cout<<amount<<endl; } int main() { int T; cin>>T; int d; for(int i=1;i<=T;i++){ cin>>amount>>n>>d; work(d); } return 0; }