> #include <iostream>
> #define MAX(A, B) (A) > (B)? (A):(B)
> using namespace std;
> int f[101000];
> struct money
> {
> 	int mone;
> 	int increa;
> }p[20];
> int main()
> {
> 	int t;
> 	cin >> t;
> 	while (t--)
> 	{
> 		int n, year;
> 		cin >> n >> year;
> 		int m;
> 		cin >> m;
> 		for (int k = 1; k <= m; ++k)
> 		{
> 			cin >> p[k].mone >> p[k].increa;
> 			p[k].mone /= 1000;
> 		}
> 		int temp = n;
> 		n /= 1000;
> 		while (year--)
> 		{
> 			int i;
> 			memset(f, 0, sizeof(f));
> 			for (i = 1; i <= m; ++i)
> 			{
> 				for (int j = p[i].mone; j <= n; ++j)
> 				{
> 					f[j] = MAX(f[j], f[j-p[i].mone] + p[i].increa);
> 				}
> 			}
> 			temp += f[n];
> 			n = temp/1000;
> 		}
> 		cout << temp << endl;
> 	}
> 	return 0;
> }