#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;struct node{ int v,a,b,c;}kt[111];int s,n,dp[1111];bool cmp(node x,node y){ return x.b<y.b;}int main(){ int T; scanf("%d",&T);while(T--){ scanf("%d%d",&s,&n); for(int i=0;i<n;i++) { scanf("%d%d%d",&kt[i].v,&kt[i].a,&kt[i].b); kt[i].c=kt[i].a-kt[i].b; } memset(dp,0,sizeof(dp)); sort(kt,kt+n,cmp); for(int i=0;i<n;i++) for(int j=s;j>=kt[i].a;j--) { dp[j]=max(dp[j],dp[j-kt[i].c]+kt[i].v); } int sum=0; for(int i=0;i<=s;i++) sum=max(sum,dp[i]); printf("%dn",sum);} return 0;}
