#include<bits/stdc++.h>
using namespace std;
const int N=4010;
int v[N][N],w[N][N];
int s[N];
bool t[N];
int f[N];
int ans;
int main ()
{
	int n,m;
	cin>>m>>n;
	while(n--)
	{
		int a,b,c;
		cin>>a>>b>>c;
		if(!t[c]) {
		ans++;
		t[c]=1;}
		s[c]++; 
		v[ans][s[c]]=a;
		w[ans][s[c]]=b;
	}
	for(int i=1;i<=ans;i++)
	{
		for(int j=m;j>=1;j--)
		{
			for(int k=1;k<=s[i];k++)
			{
				if(j>=v[i][k]) f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);
			}
		}
	}
	cout<<f[m];
	return 0;
}