#include<bits/stdc++.h>
#pragma GCC optimize(2) 
#define ll long long
using namespace std;
const int N = 1e3+5;
const int M = 1e2+5;
ll dp[2][N];
int w[M][N],v[M][N];
int b[N];
int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int i,j,k,s1,w1,v1,t,m,n,num=0;
	cin>>i>>j;
	for(k=1;k<=j;++k)
	{
		cin>>w1>>v1>>s1;
		b[s1]++;
		w[s1][b[s1]]=w1;
		v[s1][b[s1]]=v1;
		t=max(t,s1);
	}
	for(k=1;k<=t;++k)
	{
		num++;
		//int x=num&1;
		for(n=1;n<=b[k];++n)
		{
			for(m=0;m<=i;++m)
			{
				int x=num&1;
				dp[x][m]=max(dp[x][m],dp[x^1][m]);
				if(m>=w[k][n])dp[x][m]=max(dp[x][m],dp[x^1][m-w[k][n]]+v[k][n]);
				
			}
		}
	}
	cout<<dp[num&1][i];
	return 0;


}