#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int main(){
	int m,n;
	cin>>m>>n;
	int w[n+1],v[n+1],s[n+1],tag[n+1];
	memset(tag,0,sizeof(tag));
	for(int i=1;i<=n;i++){
		cin>>w[i]>>v[i]>>s[i];
	}
	int  d[n+1][m+1];
	memset(d,0,sizeof(d));
	for(int i=1;i<=n;i++){
		d[i][0]=1;
		int gop=s[i];
		if(tag[gop]==1){
			for(int p=0;p<=m;p++)
			d[i][p]=d[i-1][p];
			continue;
		}
		for(int j=0;j<=m;j++){
			d[i][j]=d[i-1][j];
			for(int k=i;k<=n;k++){
				if(s[k]==gop&&j-w[i]>=0) d[i][j]=max(d[i][j],d[i-1][j-w[i]]+v[i]);
			}
		}
		tag[gop]=1;
	}
	cout<<d[n][m];
	getchar(); 
	return 0;
}