杭電2191

//多重背包問題
#include<stdio.h>
#include<string.h>

int cmpmax(int a,int b)//比較大小
{
 if(a>b)
  return a;
 return b;
}
void main()
{
 int T;
 int n,m,i,j,k,nn;
 int p[105],h[105],c[105];
 int dp[105];//dp[n],n錢的時候可以獲得的最大重量
 int max;
 while(scanf("%d",&T)!=EOF)//測試組
 {
  while(T--)
  {
   scanf("%d%d",&n,&m);
   for(i=1;i<=m;i++)
    scanf("%d%d%d",&p[i],&h[i],&c[i]);

   memset(dp,0,sizeof(dp));//數組歸零

   for(i=1;i<=m;i++)//m個種類的大米
   {
   
    for(k=c[i];k>=1;k--)//大米的數量
    {
     for(j=n;j>=0;j--)
     if(j>=p[i])
      dp[j]=cmpmax(dp[j],dp[j-p[i]]+h[i]);
    
    }
   }
    printf("%d\n",dp[n]);
  }
 }
}