#include<iostream>#include<cstdio>#include<algorithm>/*虽然该题不排序也可以过，但是我认为价格和重量最大的先买比较合理*/#include<cstring>#include<string>using namespace std;#define N 105int dp[N];struct Node{     int p,h,c;}num[105];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=1;i<=m;i++)            cin>>num[i].p>>num[i].h>>num[i].c;        sort(num+1,num+m+1,cmp);        memset(dp,0,sizeof(dp));        for(i=1;i<=m;i++)                    for(k=1;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 0;}