1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5  6 const int maxn = 105; 7  8 int n, m, tot; 9 int p[2005], h[2005];10 int dp[maxn];11 int solve() {12     memset(dp, 0, sizeof(dp));13     for(int i = 1; i < tot; i++) {14         for(int j = n; j >= p[i]; j--) {15             dp[j] = max(dp[j], dp[j - p[i]] + h[i]);16         }17     }18     return dp[n];19 }20 21 int main() {22     int t;23     int a, b, c;24     scanf("%d",&t);25     while(t--) {26         tot = 1;27         scanf("%d %d",&n, &m);28         while(m--) {29             scanf("%d %d %d",&a, &b, &c);30             while(c--) {31                 p[tot] = a; h[tot++] = b;32             }33         }34         printf("%d\n",solve());35     }36     return 0;37 }