#include<iostream>
#include<cstdio>
using namespace std;
int m,n,ans,cnt,MAX;
struct ahah{
int mon,vl;
int fcost[3],fvl[3];
int num;
}pre[61];
int f[600001];
int main()
{
scanf("%d%d",&n,&m);
int x,y,z;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&z);
if(z==0)
{
pre[++cnt].mon=x;pre[cnt].vl=x*y;
}
else
{
pre[z].fcost[++pre[i].num]=x;
pre[z].fvl[pre[i].num]=x*y;
}
}
for(int i=1;i<=cnt;i++)
{
for(int j=n;j>=0;j--)
{
if(j>=pre[i].mon)f[j]=max(f[j],f[j-pre[i].mon]+pre[i].vl);
if(j>=pre[i].mon+pre[i].fcost[1])f[j]
=max(f[j],f[j-pre[i].mon-pre[i].fcost[1]]+pre[i].vl+pre[i].fvl[1]);
if(j>=pre[i].mon+pre[i].fcost[2])f[j]
=max(f[j],f[j-pre[i].mon-pre[i].fcost[2]]+pre[i].vl+pre[i].fvl[2]);
if(j>=pre[i].mon+pre[i].fcost[1]+pre[i].fcost[2])f[j]
=max(f[j],f[j-pre[i].mon-pre[i].fcost[1]-pre[i].fcost[2]]+pre[i].vl+pre[i].fvl[1]+pre[i].fvl[2]);
MAX=max(MAX,f[j]);
}
}
printf("%d",MAX);
}