#include<stdio.h>
#include<string.h>
int max(int a,int b)
{
    return a>b?a:b;
}

int main ()
{
    int t;
    int n,m,i;
    int p[105],h[105],c[105],s[105];
    scanf("%d",&t);
    while(t--)
    {
        memset(s,0,sizeof(s));
        scanf("%d%d",&n,&m);
        for(i=1;i<=m;i++)
            scanf("%d%d%d",&p[i],&h[i],&c[i]);
        
        for(i=1;i<=m;i++)
            for(int j=1;j<=c[i];j++)
                for(int k=n;k>=p[i];k--)
                    s[k]=max(s[k-p[i]]+h[i],s[k]);
        printf("%d\n",s[n]);

    }
    return 0;
}