#include<bits/stdc++.h>
using namespace std;
int m,n;// 物品数量和容量 
const int N=4e4;
int f[N];
int w[N],fw[N][3];//价格 
int v[N],fv[N][3];//价值  
int z[N];//是否为主件 

int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>w[i]>>v[i]>>z[i];
		if(z[i]==0){
			v[i]*=w[i];
		}
		else{
			fw[z[i]][0]++;
			fw[z[i]][fw[z[i]][0]]=w[i];
			fv[z[i]][fw[z[i]][0]]=w[i]*v[i];
		}
	}
	for(int i=1;i<=m;i++){
		for(int j=n;j>=w[i];j--){
			f[j]=max(f[j-w[i]]+v[i],f[j]);//只要主件 
			if(j>=w[i]+fw[i][1]){//主件和附件1 
				f[j]=max(f[j-w[i]-fw[i][1]]+v[i]+fv[i][1],f[j]); 
			}
			if(j>=w[i]+fw[i][2]){//主件和附件2
				f[j]=max(f[j-w[i]-fw[i][2]]+v[i]+fv[i][2],f[j]);
			}
			if(j>=w[i]+fw[i][1]+fw[i][2]){//主件和附件1,2 
				f[j]=max(f[j-w[i]-fw[i][1]-fw[i][2]]+v[i]+fv[i][1]+fv[i][2],f[j]);
			}
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		ans=max(ans,f[i]);
	}
	cout<<f[n];
	return 0;
}