#include <iostream>
#include <cstring>
using namespace std;
int v,n,num,W,U,now=1,f[500000];
struct Node
{
    int w,u,p;
} op[5000][3];
int main()
{
    cin>>v>>n;
    for(int a=1;a<=n;a++)
    {
    cin>>W>>U>>num;
    if(num&&op[num][1].p==0)
    {
    
    op[num][1].w=W,op[num][1].u=U*W;
        op[num][1].p=1;
    }
    else if(num&&op[num][1].p==1)
    {
    op[num][2].w=W,op[num][2].u=U*W;
    op[num][2].p=1;
    }
    else
    {
    op[now][0].w=W,op[now][0].u=U*W;
    op[now++][0].p=1;
    }
    }
    memset(f,0,sizeof(f));
    for(int i=1;i<now;i++)
    for(int j=v;j>=op[i][0].w;j--)
    {
        f[j]=max(f[j],f[j-op[i][0].w]+op[i][0].u);
            if(op[i][1].p==1&&j-op[i][1].w-op[i][0].w>=0)
            {
            f[j]=max(f[j],f[j-op[i][1].w-op[i][0].w]+op[i][1].u+op[i][0].u);
            }
                    if(op[i][2].p==1&&op[i][1].p==1&&j-op[i][1].w-op[i][0].w-op[i][2].w>=0)
            {
            
                    f[j]=max(f[j],f[j-op[i][1].w-op[i][0].w-op[i][2].w]+op[i][1].u+op[i][0].u+op[i][2].u);
            }
                            if(op[i][2].p==1&&j-op[i][2].w-op[i][0].w>=0)
            {
            
                            f[j]=max(f[j],f[j-op[i][2].w-op[i][0].w]+op[i][2].u+op[i][0].u);
            }
    }
    cout<<f[v];
}