tijie

#include<bits/stdc++.h>
const int N=32000+10;
const int INF=0x3f3f3f3f;
using namespace std;
struct node{
	int w,v,w1,v1,w2,v2;
}a[100001];
int m,n,dp[N],x,y,z;
int main(){
	cin>>m>>n;
	for(int i=1;i<=n;i++){
		cin>>x>>y>>z;
		if(!z){
			a[i].w=x;
			a[i].v=x*y;
		}
		else{
			if(a[z].v1){
				a[z].w2=x;
				a[z].v2=x*y;
			}
			else{
				a[z].w1=x;
				a[z].v1=x*y;
			}
		}
	}

	for(int i=1;i<=n;i++){
		if(!a[i].v)	continue;
		for(int j=m;j>=a[i].w;j--){
			dp[j]=max(dp[j],dp[j-a[i].w]+a[i].v);
			if(j>=a[i].w+a[i].w1)
				dp[j]=max(dp[j],dp[j-a[i].w-a[i].w1]+a[i].v+a[i].v1);
			if(j>=a[i].w+a[i].w2)
				dp[j]=max(dp[j],dp[j-a[i].w-a[i].w2]+a[i].v+a[i].v2);	
			if(j>=a[i].w+a[i].w1+a[i].w2)
				dp[j]=max(dp[j],dp[j-a[i].w-a[i].w1-a[i].w2]+a[i].v+a[i].v1+a[i].v2);
		}
	}
	cout<<dp[m];
	return 0;
}