#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int v[110],w[110];
int f[110],num[110];
int main()
{
    int T,vn,n; 
    scanf("%d",&T);
    while(T--){
        memset(f,0,sizeof(f));
        scanf("%d%d",&vn,&n);//总金额 总类
        for(int i=1;i<=n;i++)//价格 重量 袋数
            scanf("%d%d%d",&v[i],&w[i],&num[i]);
        for(int i=1;i<=n;i++){
            for(int j=0;j<num[i];j++){
                for(int k=vn;k>=v[i];k--)
                    f[k]=max(f[k],f[k-v[i]]+w[i]);
            }       
        }
        printf("%d\n",f[vn]);
    }
    return 0;
}