#include <bits/stdc++.h>

using namespace std;

const int N = 65, M = 32005;
int dp[N][M], n, m, s, v[N], w[N];
vector <int> e[N];

void dfs (int p) {
	for (int j = m;j >= w[p];j--) dp[p][j] = v[p];
//	cout << p << endl;
	for (int i = 0;i < e[p].size();i++) {
		int y = e[p][i];
		dfs(y);
		for (int j = m;j >= w[p];j--) for (int z = j;z >= w[p];z--) dp[p][j] = max(dp[p][j], dp[p][z] + dp[y][j - z]);
	}
}

int main () {
	freopen("budgetb.in", "r", stdin);
	freopen("budgetb.out", "w", stdout);
	cin >> m >> n >> s;
	for (int i = 1;i <= n;i++) {
		int q;
		cin >> w[i] >> v[i] >> q;
		v[i] = v[i] * w[i];
		e[q].push_back(i);
	}
	dfs(0);
	cout << dp[0][m] << endl;
	return 0;
}