#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N=1e3+10;
const int INF=0x3f3f3f3f;
int a[N][N],w[N][N],dp[N];
//t[k][i]表示第k组的第i个 w[k][i]为重量 
int main(){
	ios::sync_with_stdio(0);
	cin>>m>>n;
	int maxn=-INF;
	for(int x,y,z,i=1;i<=n;i++){
		cin>>x>>y>>z;
		maxn=max(maxn,z);
		w[z][++w[z][0]]=y;
		a[z][w[z][0]]=x;
	} 
	for(int k=1;k<=maxn;k++){
		for(int j=m;j>=0;j--){
			for(int i=1;i<=w[k][0];i++){
				if(j>=w[k][i])dp[j]=max(dp[j],dp[j-w[k][i]]+a[k][i]);
			}
		} 
	} 
	cout<<dp[m];
	return 0;
}