#include<bits/stdc++.h>
using namespace std;
int a[1005]={0},b[1005]={0},c[1005]={0};
int x[105][1005]={0};
int y[105][1005]={0};
int A[105][1005]={0};
int B[105][1005]={0};
int s[105]={0};
int DP[105][1005]={0};
int o[105]={0};
int main()
{
	int m,n,num=0;
	cin>>m>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i]>>b[i]>>c[i];
		num=c[i];
		num=max(num,0);
	}
	int t=0,t1=0;
	for(int i=1;i<=n;i++)
	{
		x[c[i]][++t]=a[i];
		A[c[i]][++t1]=b[i];
	}
	int z=0,z1=0;
	for(int i=1;i<=num;i++)
	{
		for(int j=1;j<=1005;j++)
		{
			if(x[i][j]!=0)
			{
				y[i][++z]=x[i][j];
				B[i][++z1]=A[i][j];
			}
			s[i]=z;
		}
		z=0;
		z1=0;
	}
	/*for(int i=1;i<=num;i++)
	{
		for(int j=1;j<=s[i];j++)
		{
			cout<<"质量"<<y[i][j]<<"价值"<<B[i][j]<<" "; 
		}
		cout<<endl;
	}*/
	for(int i=1;i<=num;i++)//类的总数
	{
		for(int j=1;j<=m;j++)//背包体积
		{
			for(int k=0;k<=s[i];k++)//方案总数=每一类的物品数+1（可以一个不选） 
			{
				if(j>=y[i][k])DP[i][j]=max(DP[i][j],DP[i-1][j-y[i][k]]+B[i][k]);
				else DP[i][j]=DP[i][j];
			} 
		 } 
	}
	cout<<DP[num][m];
	return 0;
}