HD2191

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;

const int MAX_SIZE = 105;

int val[MAX_SIZE];
int weg[MAX_SIZE];
int num[MAX_SIZE];
int dp[MAX_SIZE];

int main()
{
    int m;
    scanf("%d", &m);

    while(m--)
    {
        int v, n;
        scanf("%d %d", &v, &n);

        for(int i = 0; i < n; i++)
        {
            scanf("%d %d %d", val+i, weg+i, num+i);
        }

        memset(dp, 0, sizeof(dp));

        for(int i = 0; i < n; i++)
        {
            if(val[i]*num[i] >= v)
            {
                for(int j = val[i]; j <= v; j++)
                {
                    dp[j] = max(dp[j], dp[j-val[i]] + weg[i]);
                }
                continue;
            }

            int k = 1;
            while(k < num[i])
            {
                for(int j = v; j - k*val[i] >= 0; j--)
                {
                    dp[j] = max(dp[j], dp[j-val[i]*k] + k*weg[i]);
                }
                num[i] -= k;
                k *= 2;
            }
            for(int j = v; j - num[i]*val[i] >= 0; j--)
            {
                dp[j] = max(dp[j], dp[j-val[i]*num[i]] + num[i]*weg[i]);
            }
        }
        printf("%d\n", dp[v]);
    }
    return 0;
}