#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#define v first
#define w second
using namespace std;
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() {
    cin >> m >> n;//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};//如果是0，表示为主件 
        else servent[q].push_back({v, p});//如果不是0，为附件，插入相关主键 
    }
    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)
                    {//如果第k位是1，那就说明选第k个 
                        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] << endl;
    return 0;
}

#include<iostream>
#include<vector>
#define v first
#define w second
using namespace std ;
typedef pair<int,int>PII;
const int N=32100;
int f[N];
int n,m;
vector<PII>servent[N];
PII master[N];
int main()
{
    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].push_back({v,p});
    }
    for(int i=1;i<=n;i++)
        for(int j=m;j>=0;j--)
            for(int k=0;k< 1<<servent[i].size();k++)
            {
                int w=master[i].w,v=master[i].v;
                for(int u=0;u<servent[i].size();u++)
                {
                    if(k>>u&1)
                    {
                        w+=servent[i][u].w;
                        v+=servent[i][u].v;
                    }
                }
                if(j>=v)
                    f[j]=max(f[j],f[j-v]+w);
            }
    cout<<f[m]<<endl;
    return 0;
}