#include<iostream>

#include<cstdio>

#include<algorithm>

/*

虽然该题不排序也可以过，但是我认为价格和重量最大的先买比较合理

*/

#include<cstring>

#include<string>

using namespace std;

#define N 105

int dp[N];

struct Node{

     int p,h,c;

}num[];

bool cmp(Node a,Node b){

    return a.h*b.p>a.p*b.h;

}

int main(void)

{

    int n,m;

    int i,j,k;

    int c;

    cin>>c;

    while(c--){

        cin>>n>>m;

        for(i=;i<=m;i++)

            cin>>num[i].p>>num[i].h>>num[i].c;

        sort(num+,num+m+,cmp);

        memset(dp,,sizeof(dp));

        for(i=;i<=m;i++)

            for(k=;k<=num[i].c;k++){

                for(j=n;j>=num[i].p;j--){

                    dp[j]=max(dp[j],dp[j-num[i].p]+num[i].h);

                }

            }

        cout<<dp[n]<<endl;

    }

    return ;

}