#include <iostream>
#include <algorithm>
using namespace std;
int n,m;
int value[65];  //价格*重要度
int cost[65];  //价格
int dp[65][32005];  //dp[i][j]表示前i个物品在总钱数不超过j的情况下value总和的最大值
int fans[65];  //附属商品的个数
int follow[65][3];//对于主商品，follow[i][1]是第一个附属商品的编号
int main()
{
    cin>>n>>m;
    int v,p,q;
    for(int i=1;i<=m;i++) 
    {
        cin>>v>>p>>q;
        cost[i]=v;
        value[i]=v*p;
        if(q!=0)  //不是主商品
            follow[q][++fans[q]]=i;
    }
    int pre=0;  //上次展开的主商品编号
    for(int i=1;i<=m;i++) 
        if(fans[i]) //如果有附属商品，即i是主商品，在展开讨论
            for(int j=0;j<=n;j++)  //主商品i，附属商品fan1,fan2
            {
                dp[i][j]=dp[pre][j];  //跳过该商品，对应01背包dp[i][j]=dp[i-1][j]
                int fan1=(fans[i]>=1)?follow[i][1]:-1;//取出两个附件编号
                int fan2=(fans[i]>=2)?follow[i][2]:-1;
                if(j-cost[i]>=0) dp[i][j]=max(dp[i][j],dp[pre][j-cost[i]]+value[i]);
                    //只要主商品
                if(fan1!=-1 && j-cost[i]-cost[fan1]>=0)  //主+fan1
                    dp[i][j]=max(dp[i][j],dp[pre][j-cost[i]-cost[fan1]]+value[i]+value[fan1]);
                if(fan2!=-1 && j-cost[i]-cost[fan2]>=0)  //主+fan2
                    dp[i][j]=max(dp[i][j],dp[pre][j-cost[i]-cost[fan2]]+value[i]+value[fan2]);
                if(fan1!=-1 && fan2!=-1 && j-cost[i]-cost[fan1]-cost[fan2]>=0)
                    dp[i][j]=max(dp[i][j],dp[pre][j-cost[i]-cost[fan1]-cost[fan2]]+value[i]+value[fan1]+value[fan2]);
                pre=i;
            }
    cout<<dp[m][n];
}