/*
题意：初始时有m ( m<=10000 ) 美元,现在有n只股票,每只股票如果购买一份的话当前的利润也给出了( 可以无限购买 )。
假设你第一年用m美元买了股票,这年结束的时候你就会把所有股票原价卖出并且得到你所有股票的利润. 然后你又开始第2年股票的投资了...( 股票的价格都是 1000 的整数倍 , 且每只股票的年收益率 <=10% )
现在你需要连续买t年( t<=40 ) 的股票，问t年后你的总钱数是多少。
分析 :由于有n只股票且每只股票可以无限买，所以本题可以把每一年的投资看成是一个完全背包问题。然后用前一年的利润+本钱继续进行下一年的投资( 又是一个完全背包过程 )。
*/

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <cstdio>
#include <fstream>

int CompleteKnapsack(int *w, int* v, int n, int weight, int** f, int* x = NULL)
{
	for (int i = 0; i < 2; i++)
	{
		memset(f[i], 0, sizeof(int)*(weight + 1));
	}
	int** fk = NULL;
	fk = new int*[n];
	for (int i = 0; i < n; i++)
	{
		fk[i] = new int[weight + 1];
	}
	if (fk)
	{
		for (int i = 0; i < n; i++)
		{
			memset(fk[i], 0, sizeof(int)*(weight + 1));
		}
	}
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j <= weight; j++)
		{
			if (j < w[i])
			{ 
				f[(i + 1) % 2][j] = f[i % 2][j];
				if (fk)
				{
					fk[i][j] = 0;
				}
			}
			else
			{
				if (f[i % 2][j] > f[(i + 1) % 2][j - w[i]] + v[i])
				{
					f[(i + 1) % 2][j] = f[i % 2][j];
					if (fk)
					{
						fk[i][j] = 0;
					}
				}
				else
				{
					f[(i + 1) % 2][j] = f[(i + 1) % 2][j - w[i]] + v[i];
					if (fk)
					{
						fk[i][j] = fk[i][j - w[i]] + 1;
					}
				}
			}
		}
	}

	if (x)
	{
		int j = weight;
		for (int i = n - 1; i >= 0; i--)
		{
			x[i] = fk[i][j];
			j -= fk[i][j] * w[i];
		}
	}

	for (int i = 0; i < n; i++)
	{
		delete[] fk[i];
	}
	delete[] fk;

	return f[n % 2][weight];
}

int main()
{
	int caseCount = 0;
	scanf("%d", &caseCount);
	for (int index = 0; index < caseCount; index++)
	{
		int total = 0;
		int year = 0;
		int n = 0;
		scanf("%d%d%d", &total, &year, &n);
		int* x = NULL;
		x = new int[n];
		int* w = new int[n];
		int* v = new int[n];
		int** f = new int*[2];
		for (int i = 0; i < 2; i++)
		{
			f[i] = new int[total + 1];
		}
		for (int i = 0; i < n; i++)
		{
			scanf("%d%d", &w[i], &v[i]);
			w[i] /= 1000;
		}
		for (int i = 0; i < year; i++)
		{
			int weight = total / 1000;
			int current = CompleteKnapsack(w, v, n, weight, f, x);

			//printf("\n");
			//for (int j = 0; j < n; j++)
			//{
			//	printf("%d ", x[j]);
			//}
			
			total += current;

			//printf("\n%d\n\n", total);
		}
		for (int i = 0; i < 2; i++)
		{
			delete[] f[i];
		}
		delete[] f;
		delete[] v;
		delete[] w;
		delete[] x;
		printf("%d\n", total);
	}
	return 0;
}