#include<bits/stdc++.h>
using namespace std;
int m,n;
const int N=1e3+2;
int maxn=0;;
int dp[N][N],s[101],v[101][N],w[101][N];
signed main(){
	cin>>m>>n;
	for(int i=1;i<=n;i++){
		int a,b,c;
		cin>>a>>b>>c;
		s[c]++;
		v[c][s[c]]=b;
		w[c][s[c]]=a;
		maxn=max(maxn,c);
	}
	for(int i=1;i<=maxn;i++){
	//	if(s[c]){
			for(int j=0;j<=m;j++){
				for(int k=1;k<=s[i];k++){
					if(j>=w[i][k]){
						dp[i][j]=max(dp[i][j],dp[i-1][j-w[i][k]+v[i][k]]);
					}
				}
			}
	//	}
	}
	cout<<dp[maxn][m];
	return 0;
}