#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,a[10001],b[10001],c[10001],g,f[10001],t[10001];
vector<ll>v[1001],v1;
int main(){
	cin>>m>>n;
	for (ll i=1;i<=n;i++){
		cin>>a[i]>>b[i]>>c[i];
		if (t[c[i]]==0) g++,t[c[i]]++,v1.push_back(c[i]);
		v[c[i]].push_back(i);
	}
	for (ll k=1;k<=g;k++)
	for (ll j=m;j>=0;j--)
	for (ll i=0;i<v[v1[k-1]].size();i++){
		ll id=v[k][i];
		if (a[id]<=m) f[j]=max(f[j],f[j-a[id]]+b[id]); 
	}
	cout<<f[m];
}