#include<bits/stdc++.h>
using namespace std;
int dp[85][10005]={},n,zu[85][5],cost[85],vlu[85],money,zu_i_sum[85]={},zu_sum=0;
int main()
{
	cin>>money>>n;
	for(int i=1,l=1;l<=n;i++,l++){
		int z,v;
		cin>>cost[i]>>v>>z;
		vlu[i]=v*cost[i];
		if(z!=0){
			cost[i]+=cost[z+(i-l)];
			vlu[i]+=vlu[z+(i-l)];
			zu_i_sum[z]++;
		    zu[z][zu_i_sum[z]]=i;
		    if(zu_i_sum[z]==3){
		    	i++;
		    	zu_i_sum[z]++;
		    	cost[i]=cost[zu[z][1]];
			    vlu[i]=vlu[zu[z][1]];
		    	for(int j=2;j<=3;j++){
		    		cost[i]+=cost[zu[z][j]]-cost[zu[z][1]];
			        vlu[i]+=vlu[zu[z][j]]-vlu[zu[z][1]];
				}
			}
		}
		else{
			zu_sum=max(zu_sum,l);
			zu_i_sum[l]++;
		    zu[l][1]=i;
		}
	}
	for(int i=1;i<=zu_sum;i++){
		for(int j=1;j<=money;j++){
		    dp[i][j] = max(dp[i][j], dp[i-1][j]);
			for(int k=1;k<=zu_i_sum[i];k++){
				if(j-cost[zu[i][k]]>=0){
					dp[i][j]=max(dp[i][j],vlu[zu[i][k]]+dp[i-1][j-cost[zu[i][k]]]);
				}
			}
		}
	}
	cout<<dp[zu_sum][money];
    return 0;
}