//多重背包问题
#include
#include
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]);
}
}
}