#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define for1(i,a,b) for(ll i=(ll)a;i<=(ll)b;++i)
#define for0(i,a,b) for(ll i=(ll)a;i>=(ll)b;--i)
ll n, m, maxx, x, y, z, w[1010][1010], v[1010][1010], u[1010], dp[10000010];
int main (){
	cin >>n >>m;
	for1 (i, 1, m){
		cin >>x >>y >>z, maxx = max (maxx, z);
		w[++ u[z]][i] = x, v[u[z]][i] = y;
	}
	for1 (i, 1, maxx){
		for0 (k, n, 0){
			for1 (j, 1, u[i]){
				if (k >= w[j][i]) dp[k] = max (dp[k], dp[k-w[j][i]]+v[j][i]);
			}
		}
	}
	cout <<dp[n];
	return 0;
}