#include<bits/stdc++.h>
using namespace std;
int n,m,i,j,a[100],b[100],x[100],t[100],dp[500010],va[100][3];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>m>>n;
	for(i=1;i<=n;i++){
		cin>>a[i]>>b[i]>>x[i];
		if(x[i])va[x[i]][++t[x[i]]]=i;
	}
	for(i=1;i<=n;i++)
		if(!x[i])
			for(j=m;j>=0;j--){
				int s1=0,s2=0,s3=0,s4=0;
				if(j-a[i]>=0)s1=dp[j-a[i]]+b[i]*a[i];
				if(t[i]>0){
					if(t[i]==1){
						if(j-a[i]-a[va[i][1]]>=0)s2=dp[j-a[i]-a[va[i][1]]]+b[i]*a[i]+b[va[i][1]]*a[va[i][1]];
					}
					else{
						if(j-a[i]-a[va[i][1]]>=0)s2=dp[j-a[i]-a[va[i][1]]]+b[i]*a[i]+b[va[i][1]]*a[va[i][1]];
						if(j-a[i]-a[va[i][2]]>=0)s3=dp[j-a[i]-a[va[i][2]]]+b[i]*a[i]+b[va[i][2]]*a[va[i][1]];
						if(j-a[i]-a[va[i][1]]-a[va[i][2]]>=0)s4=dp[j-a[i]-a[va[i][1]]-a[va[i][2]]]+b[i]*a[i]+b[va[i][1]]*a[va[i][1]]+b[va[i][2]]*a[va[i][2]];
					}
				}
				dp[j]=max(dp[j],max(s1,max(s2,max(s3,s4))));
			}
	cout<<dp[m];
}