#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

#define v first 
#define w second 

using namespace std;

const int N=60,M=32010;
typedef pair<int,int> PII;

vector<PII> s[N];
PII m[N];
int f[M];

int main()
{
    int n,nm;
    cin>>nm>>n;

    for(int i=1;i<=n;i++)
    {
        int v,w,q;
        cin>>v>>w>>q;
        if(!q) m[i].v=v,m[i].w=w*v;
        else s[q].push_back({v,w*v});
    }

    for(int i=1;i<=n;i++)
    {
        for(int j=nm;j>0;j--)
        {
            for(int l=0;l<(1<<s[i].size());l++)
            {
                int v=m[i].v,w=m[i].w;
                for(int k=0;k<s[i].size();k++)
                {
                    if(l >> k & 1)
                    {
                        v+=s[i][k].v;
                        w+=s[i][k].w;
                    }
                }
                if(j>=v) f[j]=max(f[j],f[j-v]+w);
            }
        }
    }

    cout<<f[nm]<<endl;

    return 0;
}