#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e4+10;
int dp[70][32000],v[N],w[N],kk[N][2];
bool ff[N];
signed main(){
//	freopen(".out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t,n;
	cin>>t>>n;
	for(int i=1;i<=n;i++){
		int sd,df;
		cin>>v[i]>>sd>>df;
//		df=0;
		w[i]=sd*v[i];
		if(df!=0){
			if(kk[df][0]==0){
				kk[df][0]=i;
			}
			else{
				kk[df][1]=i;
			}
		}
		else{
			ff[i]=1;
		}
	}
//	for(int i=1;i<=n;i++){
//		cout<<v[i]<<" "<<w[i]<<" "<<kk[i][0]<<" "<<kk[i][1]<<"\n";
//	}
	int sum=0;
	for(int i=1;i<=n;i++){
		if(ff[i]==1){
//			cout<<i<<" ";
			sum++;
			for(int j=1;j<=t;j++){
				dp[sum][j]=dp[sum-1][j];
				if(j>=v[i]){
					dp[sum][j]=max(dp[sum][j],dp[sum-1][j-v[i]]+w[i]);
				}
				if(kk[i][0]==1){
					if(j>=v[i]+v[kk[i][0]]){
						dp[sum][j]=max(dp[sum][j],dp[sum-1][j-v[i]-v[kk[i][0]]]+w[i]+w[kk[i][0]]);
					}
				}
				if(kk[i][1]==1){
					if(j>=v[i]+v[kk[i][1]]){
						dp[sum][j]=max(dp[sum][j],dp[sum-1][j-v[i]-v[kk[i][1]]]+w[i]+w[kk[i][1]]);
					}
					if(j>=v[i]+v[kk[i][1]]+v[kk[i][0]]){
						dp[sum][j]=max(dp[sum][j],dp[sum-1][j-v[i]-v[kk[i][1]]-v[kk[i][0]]]+w[i]+w[kk[i][1]]+w[kk[i][0]]);
					}
				}
//				cout<<dp[sum][j]<<" ";
			}
//			cout<<"\n"; 
		}
	}
	cout<<dp[sum][t];
	return 0;
}