#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;
}