//* Problem  : 1512 - Investment
//* Contest  : acm.tju.edu.cn
//* Origin   : Northwestern European 2004
//* Type     : Solution
//* Date     : 2007.08.21
//* Author   : alt
//* Language : C++
//* Compiler : Microsoft Visual C++ 6.0
//* Algoritm : Knapsack

#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>

int n, m, k;
int a[10], b[10];

int r[50001];

void fill_knapsack()
{
	const int max = 50000;
	int i, j;
	memset(r, 0, sizeof(r));
	for (i = 0; i < k; i++)
		if (r[a[i]] < b[i])
			r[a[i]] = b[i];
	for (i = 0; i < max; i++)
		if (r[i])
			for (j = 0; j < k; j++)
				if (i + a[j] <= max && r[i] + b[j] > r[i+a[j]])
					r[i+a[j]] = r[i] + b[j];
	for (i = 1; i <= max; i++)
		if (r[i] < r[i-1])
			r[i] = r[i-1];

}

int solve()
{
	fill_knapsack();
	for (int i = 0; i < m; i++)
		n += r[n/1000];
	return n;
}

int main()
{
	int i, nt, res;
	scanf("%d", &nt);
	while (nt--)
	{
		scanf("%d %d %d", &n, &m, &k);
		for (i = 0; i < k; i++)
		{
			scanf("%d %d", &a[i], &b[i]);
			a[i] /= 1000;
			if (a[i] > 46000) 
			{
				b[i] = 0;
				a[i] = 0;
			}
		}
		res = solve();
		printf("%d\n", res);
	}
	return 0;
}