# include <bits/stdc++.h> using namespace std ; int t , amount , n , d ; int weight [12] , profit [12] , dp [1000002] ; int main ( ) { cin >> t ; while ( t -- ) { memset ( dp , 0 , sizeof ( dp ) ) ; cin >> amount >> n >> d ; for ( int i = 0 ; i < d ; i ++ ) { cin >> weight [i] >> profit [i] ; weight [i] /= 1000 ; } for ( int i = 0 ; i < n ; i ++ ) { int t1 = amount / 1000 ; for ( int j = 0 ; j < d ; j ++ ) { for ( int k = weight [j] ; k <= t1 ; k ++ ) { dp [k] = max ( dp [k] , dp [k - weight [j]] + profit [j] ) ; } } amount += dp [t1] ; } cout << amount << endl ; } return 0 ; }