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