#include <iostream>
#include <string.h>
#include <iomanip>
#include <algorithm>
#include <math.h>
using namespace std;

int dp[1005];
int mg[1005];
int va[1005];
int gro[1005];

int m,n;
int grn=0;
int main(){
	cin>>m>>n;
	for(int i=1;i<=n;i++){
		cin>>mg[i]>>va[i]>>gro[i];
		grn=max(grn,gro[i]);
	}
	for(int i=1;i<=grn;i++){
		for(int j=m;j>=0;j--){
			for(int k=1;k<=n;k++){
				if(gro[k]!=i||j<mg[k]) continue;
				dp[j]=max(dp[j],dp[j-mg[k]]+va[k]);
			
			}
		}
	}
	cout<<dp[m];
	return 0;
}