cpp
#include<bits/stdc++.h>
using namespace std;
int n, m;
int c[105][3], w[105][3], dp[32005];
int main(){
	cin >> n >> m;
	int cnt = 1;
	for (int i = 1; i <= m; i++) {
		int v, p, q;
		cin >> v >> p >> q;//v 价格, p 重要度, q 从属关系 
		if (!q) {
			c[cnt][0] = v;
			w[cnt][0] = v * p;
			cnt++;
		}
		else {
			if (c[q][1]){
				c[q][2] = v;
				w[q][2] = v * p;
			} 
			else {
				c[q][1] = v;
				w[q][1] = v * p;
			}
		}
	}
	cnt--;
	for (int i = 1; i <= cnt; i++) {
		for (int j = n; j >= 0; j--) {
			int temp = dp[j];
			if (j >= c[i][0]) {
				dp[j] = dp[j - c[i][0]] + w[i][0];
				for (int k = 1; k <= 2; k++) {
					if (j - c[i][0] >= c[i][k])
					dp[j] = max(dp[j - c[i][0] - c[i][k]] + w[i][k] + w[i][0], dp[j]);
				}
				if (j - c[i][0] - c[i][1] - c[i][2] >= 0) {
					dp[j] = max(dp[j], dp[j - c[i][0] - c[i][1] - c[i][2]] + w[i][0] + w[i][1] + w[i][2]);
				}
			}
			dp[j] = max(dp[j], temp);
		}
	}
	cout << dp[n] << endl;
	return 0;
}