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

/*
  zw:主件价格,zv:主件价格*重要度
  fw:主件对应附件价格(第1列是个数，第23列是第几个附件)
  fv:附件价格*重要度
  dp：滚动存储每种情况下每个单位价格下的最大结果 
  n:总价格,m:总个数 
*/

int m,total;//m:件数,total:总金额 
int zw[40000],zv[40000];//主件金额，主件价值(金额*重要度) 
int fw[40000][4],fv[40000][3];//附件金额，附件价值 
int dp[40000],v,p,q;//dp:存储在i件物品的背包容量为j的情况下的最大价值 
int main(){
	int i,j;
	cin>>total>>m;
	//循环m件物品 
	for(i = 1;i <= m;i++){
		cin>>v>>p>>q;
		//如果是主件 
		if(q == 0){
			zw[i] = v;//价格 
			zv[i] = v * p;//价值度（价格*重要） 
		}else{
			//第q个物品的附件个数 
			fw[q][0]++;
			fw[q][fw[q][0]]=v;//第几个主件的价格
			fv[q][fw[q][0]]=v*p;//附件价值(价格*重要) 
		} 
	}
	
	//循环m个物品
	for(i = 1;i <= m;i++){
		//按背包的逻辑循环从总价格开始循环到每个主件的价格 
		for(j = total;j >= zw[i];j--){
			//在能装下这个物品的情况下，讨论：只要主件，主件+附件1，主件+附件2，主件+附件12
			//情况1：只要主件
			dp[j] = max(dp[j],dp[j-zw[i]]+zv[i]);
			//情况2：主件+附件1
			if(j>=zw[i]+fw[i][1]) dp[j]=max(dp[j],dp[j-zw[i]-fw[i][1]]+zv[i]+fv[i][1]);
			//情况3：主件+附件2
			if(j>=zw[i]+fw[i][2]) dp[j]=max(dp[j],dp[j-zw[i]-fw[i][2]]+zv[i]+fv[i][2]);
			//情况4：主件+附件12
			if(j>=zw[i]+fw[i][1]+fw[i][2]) 
			 dp[j]=max(dp[j],dp[j-zw[i]-fw[i][1]-fw[i][2]]+zv[i]+fv[i][1]+fv[i][2]);
		}
	} 
	cout<<dp[total];
	return 0;
}

/**************************************************************
	Problem: 1820
	User: admin
	Language: C++
	Result: Accepted
	Time:68 ms
	Memory:3636 kb
****************************************************************/