#include <bits/stdc++.h>
using namespace std;
int m,n,a[100001],b[100001],c,dp[100001],d[10001][10001],id,sum,gs[10005];
int main()
{
	cin>>m>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i]>>b[i]>>c;
		id=max(id,c);
		gs[c]++;
		d[id][gs[id]]=i;
	}
	for(int i=1;i<=id;i++) 
	{
		for(int j=m;j>=0;j--) 
		{
			for(int k=1;k<=gs[i];k++) 
			{
				int f=d[i][k];
				if(j>=a[f])
				{
					dp[j]=max(dp[j],dp[j-a[f]]+b[f]);
				}
			}
		}
	}
	cout<<dp[m];
	return 0;
}