#include<bits/stdc++.h>
using namespace std;
struct f{
	int t,w,z;
}a[1020];
int zz[1020],c[1020],dz[1020][1020];
int main(){
	int t,n,s=0;
	cin>>t>>n;
	for(int i=1;i<=n;++i)
	{
		cin>>a[i].t>>a[i].w>>a[i].z;
		s=max(s,a[i].z);
		zz[a[i].z]+=1;
		dz[a[i].z][zz[a[i].z]]=i;
	}
	for(int i=1;i<=s;i++)
		for(int j=t;j>=0;j++)	
			for(int k=1;k<=zz[i];k++)	
				if(j>=a[dz[i][k]].t)
					c[j]=max(c[j],c[j-a[dz[i][k]].t]+a[dz[i][k]].w);
	cout<<c[t];
	return 0;
}