#include <bits/stdc++.h>
using namespace std;
const int maxn=4e4+5;
int n,m,s;
int v[70],p[70],q[70],a[70],b[70],c[70];
int b1[70],b2[70],c1[70],c2[70];
int f[70];
int dp[70][maxn],num;
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;++i){
		cin>>v[i]>>p[i]>>q[i];
		if(q[i]==0)a[i]=v[i]*p[i];
		else{
			f[q[i]]++;
			if(f[q[i]]==1){
				b[q[i]]=v[i]*p[i];
				b1[q[i]]=v[i];
				b2[q[i]]=p[i];
			}
			else if(f[q[i]]==2){
				c[q[i]]=v[i]*p[i];
				c1[q[i]]=v[i];
				c2[q[i]]=p[i];
			}
		}
	}
	for(int i=1;i<=m;++i){
		if(q[i]==0){
			for(int j=1;j<=n;++j){
//				cout<<"j:"<<j<<endl;
				if(f[i]==0){
					dp[i][j]=dp[i-1][j];
					if(j>=v[i]){
						dp[i][j]=max(dp[i][j],dp[i-1][j-v[i]]+a[i]);
//						cout<<1<<' '<<dp[i][j]<<' '<<dp[i-1][j]<<' '<<a[i]<<' '<<dp[i-1][j-v[i]]<<endl;
					}
				}
				else if(f[i]==1){
					dp[i][j]=dp[i-1][j];
					if(j>=v[i]&&j<(v[i]+b1[i])){//
						dp[i][j]=max(dp[i][j],dp[i-1][j-v[i]]+a[i]);
					}
					if(j>=v[i]+b1[i])dp[i][j]=max(dp[i][j],dp[i-1][j-v[i]-b1[i]]+a[i]+b[i]);
				}
				else if(f[i]==2){
					dp[i][j]=dp[i-1][j];
					if((j>=v[i]&&j<(v[i]+b1[i]))||(j>=v[i]&&j<(v[i]+c1[i]))){//
						dp[i][j]=max(dp[i][j],dp[i-1][j-v[i]]+a[i]);
//						cout<<3<<' '<<dp[i][j]<<' ';
					}
					if(j>=v[i]+b1[i]&&j<v[i]+b1[i]+c1[i]){//
						dp[i][j]=max(dp[i][j],dp[i-1][j-v[i]-b1[i]]+a[i]+b[i]);
//						cout<<4<<' '<<dp[i][j]<<' ';
					}
					if(j>=v[i]+c1[i]&&j<v[i]+b1[i]+c1[i]){//
						dp[i][j]=max(dp[i][j],dp[i-1][j-v[i]-b1[i]]+a[i]+c[i]);
//						cout<<5<<' '<<dp[i][j]<<' ';
					}
					if(j>=v[i]+b1[i]+c1[i]){
						dp[i][j]=max(dp[i][j],dp[i-1][j-v[i]-b1[i]-c1[i]]+a[i]+b[i]+c[i]);
//						cout<<6<<' '<<dp[i][j]<<' ';
					}
//					cout<<2<<' '<<dp[i][j]<<' ';
				}
//				cout<<endl;
			}
		}
		else{
			for(int j=1;j<=n;++j)dp[i][j]=dp[i-1][j];
		}
	}
//	for(int i=1;i<=m;++i){
//		for(int j=1;j<=n;j++)cout<<dp[i][j]<<' ';
//		cout<<endl;
//	}
	cout<<dp[m][n]<<endl;
	return 0;
}