#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

#define N 20005

int dp[N], p[N], w[N], m[N];

int main ()
{
    int t, price, n;

    scanf ("%d", &t);

    while (t--)
    {
        memset (dp, 0, sizeof (dp));

        scanf ("%d %d", &price, &n);
        int k = 1, x, y, z;
        for (int i=1; i<=n; i++)
        {
            scanf ("%d %d %d", &x, &y, &z);

            int cnt = 0;
            for (int j=1; j<=z; j*=2)
            {
                p[k] = x*j, w[k++] = y*j;
                cnt+=j;
                if(cnt+j*2 > z)
                {
                    p[k] = x*(z-cnt), w[k++] = y*(z-cnt);
                    break;
                }
                    
            }
        }

        for (int i=1; i<k; i++)
        {
            for (int j=price; j>=p[i]; j--)
                dp[j] = max (dp[j], dp[j-p[i]] + w[i]);
        }
        printf ("%d\n", dp[price]);
    }
    return 0;
}