#include<bits/stdc++.h>
using namespace std;
int m,n,a[100001],b[100001],c[1001];
int f[1000001];
int t,cc[10001];
int zu;
int main(){
	cin>>m>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i]>>b[i]>>t;
		zu=max(zu,t);
		cc[t]++;
		c[cc[t]]=i;
	}
	for(int q=1;q<=zu;q++){
	for(int j=m;j>=0;j--){
		for(int i=1;i<=cc[q];i++){
             if(j>=a[c[i]]) f[j]=max(f[j],f[j-a[c[i]]]+b[c[i]]);
		}
	}
}
	cout<<f[m];
	
}