#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<set>
#include<string>
#include<stack>
#include<queue>
using namespace std;
struct node{
	int zv,zp;
	int fv1,wv1;
	int fv2,wv2;
};
node a[35000];
int maxn,n;
int vi,pi,qi;
int dp[35000];
int main(){
   cin>>maxn>>n;
   for(int i=1;i<=n;i++){
   	cin>>vi>>pi>>qi;
   	    if(qi==0){
   			a[i].zv=vi;
   			a[i].zp=vi*pi;
		   }
		else{
		   	if(a[qi].wv1==0){
		   		a[qi].fv1=vi;
				a[qi].wv1=vi*pi; 
				} 
		   	else{
		   		a[qi].fv2=vi;
				a[qi].wv2=vi*pi;
			   }
		   }
    }
  	for(int i=1;i<=n;i++){
  		if(a[i].zp==0) continue;
  		for(int j=maxn;j>=a[i].zv;j--){
  			dp[j]=max(dp[j],dp[j-a[i].zv]+a[i].zp);
  			if(a[i].zv+a[i].fv1<=j) 		//在a[i].zp卡 
			  dp[j]=max(dp[j],dp[j-a[i].zv-a[i].fv1]+a[i].zp+a[i]+wv1);
		 	if(a[i].zv+a[i].fv2<=j)
			  dp[j]=max(dp[j],dp[j-a[i].zv-a[i].fv2]+a[i].zp+a[i]+wv2);
			if(a[i].zv+a[i].fv1+a[i].fv2<=j) 
			  dp[j]=max(dp[j],dp[j-a[i].zv-a[i].fv1-a[i].fv2]+a[i].zp+a[i]+wv1+a[i].wv2);		 
	    }
	}
	cout<<dp[n];
	return 0;
}