#include<iostream> using namespace std; const int N = 20, M = 1e7 + 10; int t, n, m, d, w[N], v[N], f[M]; int main(){ cin >> t; while(t--){ cin >> m >> n >> d; for(int i = 0; i < d; i++) cin >> w[i] >> v[i]; for(int i = 0; i < n; i++){ for(int j = 0; j <= m; j++) f[j] = 0; for(int j = 0; j < d; j++){ for(int k = 0; k <= m; k++){ if(k >= w[j]) f[k] = max(f[k], f[k-w[j]] + v[j]); } } m += f[m]; } cout << m << endl; } }