C :

#include <stdio.h>
#include <string.h>
#define maxc 100
#define maxv 1000
int dp[maxv]={0};
int v[maxc]={0};
int p[maxc]={0};
int c[maxc]={0};
int max(int x,int y){
	return x>y?x:y;
}
int main()
{
	int i,j,k,n,m,nn,e;
	scanf("%d",&nn);
	for(e=0;e<nn;e++){
		scanf("%d%d",&m,&n);
		memset(dp,0,sizeof(dp));
		
		for(i=0;i<n;i++){
			scanf("%d%d%d",&v[i],&p[i],&c[i]);
		}
		for(i=0;i<n;i++){
			for(j=m;j>=0;j--){
			for(k=0;k<=c[i];k++){
				if(j-k*v[i]>=0){
					dp[j]=max(dp[j],dp[j-k*v[i]]+p[i]*k);
				}
			}
			}
		}
		printf("%d\n",dp[m]);
	}
	return 0;
}