#include <bits/stdc++.h>
using namespace std;

int n,m,t;               // [1] t-测试用例组数；n-每组的粮食种类数；m-每组的总资金（元）
struct stu{
    int v,p,num;         // [2] v-该组粮食的总价格；p-该组粮食的总重量；num-该组粮食的袋数（二进制拆分后的）
}arr[1001000];           // [3] arr数组-存储二进制拆分后的所有“虚拟物品”
int dp[1001000];         // [4] dp数组-动态规划状态，dp[j]表示用j元钱能买到的最大重量

int main() {
    // 问题分析：多重背包问题，每种粮食有固定价格、重量和袋数，求m元能买的最大重量
    // 解题步骤：用二进制拆分将多重背包转化为01背包（把c袋粮食拆成1,2,4,...等份的虚拟物品），再用01背包求解
    
    cin>>t;  // [5] 读取测试用例组数
    while(t--){  // [6] 处理每组测试用例
        cin>>m>>n;  // [7] 读取当前组的资金m和粮食种类数n
        memset(dp,0,sizeof(dp));  // [8] 初始化dp数组为0（每组测试用例独立，需重置）
        int x=1,a,b,c;  // [9] x-虚拟物品的计数指针；a-单袋价格；b-单袋重量；c-该粮食的总袋数
        
        // 遍历每种粮食，进行二进制拆分
        for(int i=1;i<=n;i++){
            cin>>a>>b>>c;  // [10] 读取当前粮食的单袋价格a、单袋重量b、总袋数c
            // 二进制拆分：把c袋拆成1,2,4,...等份，每份作为一个虚拟物品
            int j=1;
            while(j<=c){
                arr[x].v = a*j;  // [11] 虚拟物品的总价格 = 单袋价格 * 份数j
                arr[x].p = b*j;  // [12] 虚拟物品的总重量 = 单袋重量 * 份数j
                arr[x++].num = j;  // [13] 记录该虚拟物品对应的袋数，x指针后移
                c -= j;  // [14] 剩余袋数减去已拆分的份数j
                j *= 2;  // [15] 份数翻倍，继续拆分
            }
            if(c){  // [16] 如果还有剩余袋数（不足2的幂次），单独作为一个虚拟物品
                arr[x].v = a*c;
                arr[x].p = b*c;
                arr[x++].num = c;
            }
        }
        
        // 01背包求解：遍历所有虚拟物品，逆序更新dp数组
        dp[0]=0;  // [17] 初始化：0元钱能买0重量
        for(int i=1;i<x;i++){  // [18] 遍历所有二进制拆分后的虚拟物品
            for(int j=m;j>=arr[i].v;j--){  // [19] 逆序遍历资金，避免重复选择同一虚拟物品
                // 状态转移：不选当前物品时dp[j]不变；选当前物品时，dp[j-arr[i].v] + arr[i].p
                dp[j] = max(dp[j], dp[j-arr[i].v] + arr[i].p);  // [20] 取两种情况的最大值
            }
        }
        cout<<dp[m]<<endl;  // [21] 输出当前组m元能买到的最大重量
    }
    return 0;
}