1 /*
 2 Author:    Leo.W
 3 Descriptipn:    買米，給出k種大米的價(jià)格、重量、最大袋數(shù)，求在m元錢下買的重量最大的米。
 4 How to Do:    多重背包問題。dp[j]=max{dp[j-k*c[i]]+k*w[i]}
 5   */
 6 #include <iostream>
 7 #include <string.h>
 8 #include <algorithm>
 9 using namespace std;
10 #define max(a,b) (a)>(b)?(a):(b)
11 int c[102],w[102],p[102];
12 int dp[102];
13 void zeroOne(int i,int n){
14     int j,k;
15     for(j=n;j>=c[i];j--){
16         for(k=1;k<=p[i];k++){
17             if(j-k*c[i]>=0)
18                 dp[j]=max(dp[j],dp[j-k*c[i]]+k*w[i]);
19         }
20     }
21 }
22 void complete(int i,int n){
23     int j,k;
24     for(j=c[i];j<=n;j++){
25         for(k=1;k<=p[i];k++){
26             if(j-k*c[i]>=0)
27                 dp[j]=max(dp[j],dp[j-k*c[i]]+k*w[i]);
28         }
29     }
30 }
31 int main(){
32     //freopen("in.txt","r",stdin);
33     int t;
34     scanf("%d",&t);
35     while (t--){
36         int i;
37         int n,m;
38         scanf("%d%d",&n,&m);
39         for(i=0;i<m;i++)    scanf("%d%d%d",&c[i],&w[i],&p[i]);
40         memset(dp,-1,sizeof(dp));
41         dp[0]=0;
42         for(i=0;i<m;i++){
43             if(c[i]*p[i]<=n)
44                 zeroOne(i,n);
45             else
46                 complete(i,n);
47         }
48         printf("%d\n",dp[n]);
49     }
50     return 0;
51 }
52