#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define v first
#define w second
#define pb push_back
typedef pair<int, int> PII;
const int N = 60, M = 32010;
int n, m;
PII master[N];
vector<PII> servent[N];
int f[M];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> m >> n;
    for(int i = 1; i <= n; i ++ )
    {
        int v,p,q;
        cin >> v >> p >> q;
        p *= v;
        if(!q) master[i] = {v,p};
        else servent[q].pb({v,p});
    }
    for(int i = 1; i <= n; i ++ )
    {
        for(int u = m; u >= 0; u -- )
        {
            for(int j = 0; j < 1 << servent[i].size(); j ++ )
            {
                int v = master[i].v, w = master[i].w;
                for(int k = 0; k < servent[i].size(); k ++ )
                    if(j >> k & 1)
                    {
                        v += servent[i][k].v;
                        w += servent[i][k].w;
                    }
                if(u >= v) f[u] = max(f[u],f[u - v] + w);
            }
        }
    }
    cout << f[m] << "\n";
    return 0;  
}