#include <bits/stdc++.h>
#define int long long
using namespace std;

int n, m;
int v[65], w[65], q[65], rec[65][32007];
bool buy[65];

int dfs(int p, int spm)
{
    if (rec[p][spm] != 0) return rec[p][spm];
    if (p > m) return 0;
    int sum = 0;
    if (spm >= v[p] && (q[p] == 0 || buy[q[p]] == 1))
    {
        buy[p] = 1;
        sum = max(sum, dfs(p + 1, spm - v[p]) + w[p] * v[p]);
        buy[p] = 0;
        sum = max(sum, dfs(p + 1, spm));
    }
    else
    {
        sum = dfs(p + 1, spm);
    }
    return rec[p][spm] = sum;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= m; i++) cin >> v[i] >> w[i] >> q[i];
    cout << dfs(1, n) << endl;
    return 0;
}

评测数据点这里，求大佬指点