#include<bits/stdc++.h>
using namespace std;
long long n,m,dp[32005],v[65][4],p[65],q[65],m1,v2[65][4];
int main(){
	freopen("2.in","r",stdin);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>v[i][++v[i][0]]>>p[i]>>q[i];
		v2[i][++v2[i][0]]=v[i][v[i][0]]*p[i];
		if(q[i]){
			v[q[i]][++v[q[i]][0]]=v[q[i]][v[q[i]][0]-1]+v[i][v[i][0]];
			v2[q[i]][++v2[q[i]][0]]=v2[q[i]][v2[q[i]][0]-1]+v2[i][v2[i][0]];
		}
	}
	for(int i=1;i<=m;i++){
		if(q[i]) continue;
		for(int j=n;j>=0;j--){
			long long x=0,y=0,z=0;
			if(j-v[i][1]>=0)
				x=max(dp[j],dp[j-v[i][1]]+v2[i][1]);
			if(j-v[i][2]>=0)	
				y=max(dp[j],dp[j-v[i][2]]+v2[i][2]);
			if(j-v[i][3]>=0)	
				z=max(dp[j],dp[j-v[i][3]]+v2[i][3]);
			dp[j]=max(dp[j],max(x,max(y,z)));
		}
	}
	cout<<dp[n];
	return 0;
}

P1064_2.in:
2000 10
500 1 0
400 4 0
300 5 1
400 5 1
200 5 0
500 4 5
400 4 0
320 2 0
410 3 0
400 3 5

P1064_2.out:
7430