#include <bits/stdc++.h>
using namespace std;
int n,m,w,v,c,dp[35001];
struct Node{
	int w,v,w1,w2,v1,v2;
	bool f;
}a[100];
int main(){
	cin >> n >> m;
	for(int i = 1;i <= m;i ++){
		cin >> w >> v >> c;
		if(c == 0){
			a[i].w = w;
			a[i].v = v;
		}else{
			if(a[c].f){
				a[c].w2 = w;
				a[c].v2 = v;
			}else{
				a[c].w1 = w;
				a[c].v1 = v;
				a[c].f = true;
			}
		}
	}
	for(int i = 1;i <= m;i ++){
		if(a[i].w * a[i].v == 0) continue;
		for(int j = n;j >= 1;j --){
			if(a[i].w + a[i].w1 <= j) dp[j] = max(dp[j],dp[j - a[i].w - a[i].w1] + a[i].w * a[i].v + a[i].w1 * a[i].v1);
			if(a[i].w + a[i].w2 <= j) dp[j] = max(dp[j],dp[j - a[i].w - a[i].w2] + a[i].w * a[i].v + a[i].w2 * a[i].v2);
			if(a[i].w + a[i].w1 + a[i].w2 <= j) dp[j] = max(dp[j],dp[j - a[i].w - a[i].w1 - a[i].w2] + a[i].w * a[i].v + a[i].w1 * a[i].v1 + a[i].w2 * a[i].v2);
		}
	}
	cout << dp[n];
	return 0;
}