Terakomari @ 2024-09-11 12:20:42
#include <bits/stdc++.h>
#include <numeric>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
#define endl '\n'
#define fi first
#define se second
#define vc vector
#define rep(i,a,b) for(int i = a;i <= b;i++)
#define uep(i,a,b) for(int i = a;i >= b;i--)
const ll mod = 998244353;
struct item {
ll v, p, q;
};
int w(item i) {
return i.v * i.p;
}
void solve() {
int n, m;
cin >> m >> n;
vector<item> it(n + 10);
vector<vector<ll>> pa(n + 10);
rep(i, 1, n) {
cin >> it[i].v >> it[i].p >> it[i].q;
if (it[i].q) {
pa[it[i].q].push_back(i);
}
}
vector<ll> f(m + 10);
rep(i, 1, n) {
auto& [v, p, q] = it[i];
if (q)continue;
uep(j, m, v) {
f[j] = max(f[j], f[j - v] + (v * p));
if (pa[i].size()) {
rep(k, 0, pa[i].size() - 1) {
if (j - v - it[pa[i][k]].v >= 0) {
f[j] = max(f[j], f[j - v - it[pa[i][k]].v] + (v * p) + w(it[pa[i][k]]));
}
}
}
}
}
cout << f[m] << endl;
}
signed main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//cout << fixed << setprecision(8);
ll T = 1;
//cin >> T;
while (T--) {
solve();
}
return 0;
}