#include<bits/stdc++.h>
using namespace std;
struct node{
	int a,b,c;
}ar[10000];
long long n,m,record[10000],dp[10000];
int dongtai(int i,int v,int chosen){
	
	if(chosen&&ar[i].c!=ar[i+1].c){
		chosen=0;
	}
	if(chosen){
		return dongtai(record[ar[i].c-1],v,chosen);
	}
	if(i<0){
		return 0;
	}
	if(dp[i]){
		return dp[i];
	}
	if(ar[i].a<=v){
		return dp[i]=max(dongtai(i-1,v,0),dongtai(i-1,v-ar[i].a,1)+ar[i].b);
	}
	return dp[i]=dongtai(i-1,v,0);
	
}
int main(){
	
	cin>>m>>n;
	for(int i=0;i<n;i++){
		cin>>ar[i].a>>ar[i].b>>ar[i].c;
		if(ar[i].c!=ar[i-1].c){
			record[ar[i].c-1]=i-1;
			for(int j=record[ar[i].c-2]+1;j<i-1;j++){
				if(ar[j].a==ar[j+1].a){
					ar[j].b=max(ar[j].b,ar[j+1].b);
					ar[j+1].a=0;
					ar[j+1].b=0;
					ar[j+1].c=0;
				}
			}
		}
	}	
	cout<<dongtai(n,m,0);
	
}

第四题TLE求救