#include<bits/stdc++.h>
using namespace std;
int dp[101][1001],n,m,f[1001];
struct group
{
	int w[101],v[101],num,maxx=INT_MIN;
}g[101];
int main()
{
	cin>>m>>n;
	int p=0;
	for(int i=1;i<=n;i++)
	{
		int a,b,c;
		cin>>a>>b>>c;
		p=max(p,c);
		g[c].maxx=max(g[c].maxx,a);
		g[c].num++;
		g[c].w[g[c].num]=a;
		g[c].v[g[c].num]=b;
	}
   	/*for(int i=1;i<=n;i++)
	{
		cout<<g[i].num<<endl;
		for(int j=1;j<=g[i].num;j++)
		{
			cout<<g[i].w[j]<<" "<<g[i].v[j]<<endl;
		}
	}*/
	/*for(int i=1;i<=p;i++)
	{
		for(int j=1;j<=m;j++)
		{
			dp[i][j]=dp[i-1][j];
			for(int k=1;k<=g[i].num;k++)
			{
				if(j-g[i].w[k]>=0)
				{
					dp[i][j]=max(dp[i][j],dp[i-1][j-g[i].w[k]]+g[i].v[k]);
				}
			}
		}
	}*/
	for(int i=1;i<=p;i++)
	{
		for(int j=m;j>=g[i].maxx;j--)//这里 
		{
			for(int k=1;k<=g[i].num;k++)
			{
				f[j]=max(f[j],f[j-g[i].w[k]]+g[i].v[k]);
			}
		}
	}
	cout<<f[m];
	//cout<<dp[p][m];
}