C++ :

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <stack>
#include <queue>
#include <cmath>
#include <string>
#include <set>
#include <map>
#define N 1010

using namespace std ;

int dp[N], w[N], c[100010] ;

int main()
{
	int t ;
	scanf ("%d", &t) ;
	while (t--)
	{
		int V, n ;
		scanf ("%d%d", &V, &n) ;
		for (int i=0; i<n; i++)
			scanf ("%d%d", &w[i], &c[i]) ;
		
		for (int i=0; i<n; i++)
			for (int v=c[i]; v<=V; v++)
				dp[v] = max (dp[v], dp[v-c[i]] + w[i]) ;
		
		printf ("%d\n", dp[V]) ;
	}

	return 0 ;
}