#include<bits/stdc++.h>

using namespace std;

const int M = 1e5+;

int dp[M];

struct node{

    int w,v;

}lis[M];

int main()

{

    int t,n,m,p,h,c,idx;

    cin>>t;

    while(t--){

        idx = ;

        cin>>n>>m;

        memset(dp,,sizeof(dp));

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

            cin>>p>>h>>c;

            int k = ;

            while(c - k>){

                c -= k;

                lis[++idx].w = k*h;

                lis[idx].v = k*p;

                k*=;

            }

            lis[++idx].w = c*h;

            lis[idx].v = c*p;

        }

        for(int i = ;i <= idx;i ++){

            for(int j = n;j >= lis[i].v;j --){

                dp[j] = max(dp[j],dp[j-lis[i].v]+lis[i].w);

            }

        }

        cout<<dp[n]<<endl;

    }

}