#include <iostream>

 #include <cstring>

 #include <cstdio>

 using namespace std;

 const int maxn =  + ;

 int w[maxn], v[maxn], num[maxn];

 int dp[maxn];

 int main()

 {

     int T, money, kind;

     while (scanf("%d", &T) != EOF)

     {

         while (T--)

         {

             scanf("%d%d", &money, &kind);

             for (int i = ; i < kind; i++)

                 scanf("%d%d%d", &v[i], &w[i], &num[i]);

             memset(dp, , sizeof(dp));

             for (int i = ; i < kind; i++)

             {

                 for (int j = ; j < num[i]; j++)    // 多了这个循环！！！

                 {

                     for (int k = money; k >= v[i]; k--)

                         dp[k] = max(dp[k], dp[k-v[i]] + w[i]);

                 }

             }

             printf("%d\n", dp[money]);

         }

     }

     return ;

 }