#include<iostream> 
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;

// 首先为每个主件建立一个组
// 其次，把对应的附件添加进组 

vector<int> v[70];
vector<int> w[70];

vector<int> fv;
vector<int> fw;
vector<int> od;

int n,m;
int f[70][32000+10];

vector<int> nv[70];
vector<int> nw[70];

int main(){
	
	for(int i=0;i<70;i++) v[i].push_back(0),w[i].push_back(0);
	
	cin>>m>>n;
	int idx=1;
	for(int i=1;i<=n;i++){
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		if(z==0){
			v[idx].push_back(x);
			w[idx].push_back(x*y);
			idx++;
		}else{ // 附件 
			fv.push_back(x);
			fw.push_back(x*y);
			od.push_back(z);
		}
	}
	
	// 把各个附件添加进组
	for(int i=0;i<od.size();i++){
	 	int no=od[i];
	 	v[no].push_back(fv[i]);
	 	w[no].push_back(fw[i]);
	}
	
	// 计算真正的组内的元素的v和w
	
	for(int i=1;i<=idx-1;i++){ // 一共有idx-1个组 
		nv[i].push_back(0);
		nw[i].push_back(0);
		if(v[i].size()==2){ // 只有主件 
			nv[i].push_back(v[i][1]);
			nw[i].push_back(w[i][1]);
		}else if(v[i].size()==3){ // 一个主件一个附件 
			nv[i].push_back(v[i][1]);
			nw[i].push_back(w[i][1]);
			
			nv[i].push_back(v[i][1]+v[i][2]);
			nw[i].push_back(w[i][1]+w[i][2]);					
		}else{ // 一个主件两个附件 
			nv[i].push_back(v[i][1]);
			nw[i].push_back(w[i][1]);
			
			nv[i].push_back(v[i][1]+v[i][2]);
			nw[i].push_back(w[i][1]+w[i][2]);

			nv[i].push_back(v[i][1]+v[i][3]);
			nw[i].push_back(w[i][1]+w[i][3]);
			
			nv[i].push_back(v[i][1]+v[i][2]+v[i][3]);
			nw[i].push_back(w[i][1]+w[i][2]+w[i][3]);
		} 
	} 
	
	for(int i=1;i<=idx-1;i++){
		for(int j=1;j<=m;j++){
			f[i][j]=f[i-1][j];
			for(int k=1;k<nv[i].size();k++){
				if(j>=nv[i][k]) f[i][j]=max(f[i][j],f[i-1][j-nv[i][k]]+nw[i][k]);
			}
		}
	}
	cout<<f[idx-1][m]<<endl;
	
	return 0;
}