#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
const int N=1e4+5;
int n,m,v[N],w[N],q[N],f[75][N][15],ans;
vector<int> pj[N]; 
int main(){
	cin>>n>>m;
	for (int i=1;i<=m;i++) {
		cin>>v[i]>>w[i]>>q[i];
		pj[q[i]].push_back(i);
	}
	int sg=0;
	for (int i=1;i<=m;i++) {
		if (q[i]) continue;
		for (int j=1;j<=n;j++) {
			f[i][j][0]=max({f[sg][j][0],f[sg][j][1],f[sg][j][2],f[sg][j][3]});
			if(j>=v[i])
			 f[i][j][1]=max({f[sg][j-v[i]][0],f[sg][j-v[i]][1],f[sg][j-v[i]][2],f[sg][j-v[i]][3]})+v[i]*w[i];
			if (pj[i].size()>=1) {
				int t=pj[i][0];
				if (j>=v[i]+v[t]) {
					int s=v[i]+v[t];
					f[i][j][2]=max({f[sg][j-s][0],f[sg][j-s][1],f[sg][j-s][2],f[sg][j-s][3]})+v[i]*w[i]+v[t]*w[t];
				}
				
			}
			if (pj[i].size()>=2) {
				int t=pj[i][1];
				if (j>=v[i]+v[t]) {
					int s=v[i]+v[t];
					int c=v[i]*w[i]+v[t]*w[t];
					f[i][j][2]=max({f[i][j][2],f[sg][j-s][0]+c,f[sg][j-s][1]+c,f[sg][j-s][2]+c,f[sg][j-s][3]+c});
				}
				int t1=pj[i][0];
				if (j>=v[i]+v[t]+v[t1]) {
					int s=v[i]+v[t]+v[t1];
					f[i][j][3]=max({f[sg][j-s][0],f[sg][j-s][1],f[sg][j-s][2],f[sg][j-s][3]})+v[i]*w[i]+v[t]*w[t]
					+v[t1]*w[t1];
				}
				
			}
		}
		for (int k=0;k<=3;k++) {
			ans=max(ans,f[i][n][k]);
		}
		sg=i;
	}
	cout<<ans;
	return 0;
}