http://acm.hdu.edu.cn/showproblem.php?pid=2191
//1337971 2009-05-04 20:46:09 Accepted 2191 15MS 268K 857 B C++ no way 
#include<iostream>
using namespace std;
struct Node
{
    int p;//价格
    int w;//重量
    int c;//数量
};
int main()
{
    int t,N,m;
    cin>>t;
    while(t--)
    {
        int i,j,k,temp;
        int dp[101];//dp[j]表示钱为j时能买的最大重量
        Node infor[101];
        cin>>N>>m;
        for(i=1;i<=m;i++)
            scanf("%d%d%d",&infor[i].p,&infor[i].w,&infor[i].c);
        for(j=0;j<infor[1].p;j++)
            dp[j] = 0;
        for(;j<=N;j++)
        {
            temp = j/infor[1].p;
            if(temp <= infor[1].c)
                dp[j] = temp * infor[1].w;
            else
                dp[j] = infor[1].c * infor[1].w;
        }

        for(i=2;i<=m;i++)//米的种类
        {
            for(j=N;j>=infor[i].p;j--)//钱的数量
            {
                for(k = 0;k<=infor[i].c;k++)//米的代数
                {
                    temp = k * infor[i].p;
                    if(temp <= j )
                    { 
                        if(dp[j-temp]+k*infor[i].w > dp[j])
                            dp[j] = dp[j-temp]+k*infor[i].w;
                    }
                    else
                        break;
                }
            }
        }
        cout<<dp[N]<<endl;
    }
    return 0;
}