#include <bits/stdc++.h>

using namespace std;
using ll = long long;

constexpr int M = 35000, inf = 0x3f3f3f3f;

ll v[M][5], p[M][5], dp[M];

int main() {
    ll n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i ++ ) {
        ll x, y, z;
        cin >> x >> y >> z;
        if (!z) {
            v[i][0] = x, p[i][0] = y;
        }
        else {
            v[z][1] ? v[z][2] = x, p[z][2] = y : v[z][1] = x, p[z][1] = y;
        }
    }

    for (int i = 1; i <= m; i ++ ) {
        for (int j = n; j >= v[i][0]; j -- ) {
            dp[j] = max (dp[j], dp[j - v[i][0]] + v[i][0] * p[i][0]);
            if (j >= v[i][0] + v[i][1]) {
                dp[j] = max (dp[j], dp[j - v[i][0] - v[i][1]] + v[i][0] * p[i][0] + v[i][1] * p[i][1]);
            }
            if (j >= v[i][0] + v[i][2]) {
                dp[j] = max (dp[j], dp[j - v[i][0] - v[i][2]] + v[i][0] * p[i][0] + v[i][2] * p[i][2]);
            }
            if (j >= v[i][0] + v[i][1] + v[i][2]) {
                dp[j] = max (dp[j], dp[j - v[i][0] - v[i][1] - v[i][2]] + v[i][0] * p[i][0] + v[i][1] * p[i][1] + v[i][2] * p[i][2]);
            }
        }
    }
    cout << dp[n] << '\n';
    return 0;
}