50pts

#include <bits/stdc++.h>
using namespace std;
const int maxn = 32005;
int dp[maxn], V, n;
int v[maxn], p[maxn], f[maxn][2], x[maxn];
int main() {
	cin >> V >> n;
	for (int i = 1; i <= n; i++) {
		cin >> v[i] >> p[i] >> x[i];
		if (x[i] != 0) {
			if (f[x[i]][0])
				f[x[i]][1] = i;
			else
				f[x[i]][0] = i;
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = V; j >= 0; j--) {
			if (x[i]) continue;
			if (j >= v[i])
				dp[j] = max(dp[j], dp[j - v[i]] + (v[i] * p[i]));
			if (f[i][0]) {
				if (j >= v[i] + v[f[i][0]])
					dp[j] = max(dp[j], dp[j - v[i] - v[f[i][0]]] + (v[i] * p[i]) + (v[f[i][0]] * p[f[i][0]]));
			}
			if (f[i][1]) {
				if (j >= v[i] + v[f[i][1]])
					dp[j] = max(dp[j], dp[j - v[i] - v[f[i][1]]] + (v[i] * p[i]) + (v[f[i][1]] * p[f[i][1]]));
			}
			if (f[i][0] && f[i][1]) {
				if (j >= v[i] + v[f[i][1]] + f[i][0])
					dp[j] = max(dp[j], dp[j - v[i] - v[f[i][1]] - v[f[i][0]]] + (v[i] * p[i]) + (v[f[i][1]] * p[f[i][1]]) + (v[f[i][0]] * p[f[i][0]]));
			}
		}
	}
	cout << dp[V] << endl;
	return 0;
}