#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int n,m,k,dp[65][32005],s[65],w[65][3],v[65][3];
int max(int a,int b)
{
if(a>=b)
return a;
else
return b;
}
int main()
{
scanf("%d%d",&n,&m);
int u,p,q;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&u,&p,&q);
if(q==0)
{
k++;
v[k][q]=u;
w[k][q]=p;
s[k]=i;
}
else
{
for(int j=1;j<=k;j++)
{
if(s[j]==q)
{
if(v[j][1]==0)
{
v[j][1]=u;
w[j][1]=p;
}
else
{
v[j][2]=u;
w[j][2]=p;
}
}
}
}
}
/*
for(int i=1;i<=k;i++)
{
cout<<"#"<<i<<endl;
printf("%d %d %d\n",v[i][0],v[i][1],v[i][2]);
printf("%d %d %d\n",w[i][0],w[i][1],w[i][2]);
}
*/
for(int i=1;i<=k;i++)
{
for(int j=0;j<=n;j++)
{
dp[i][j]=dp[i-1][j];
if(j>=v[i][0])
dp[i][j]=max(dp[i][j],dp[i-1][j-v[i][0]]+v[i][0]*w[i][0]);
if(j>=v[i][0]+v[i][1])
dp[i][j]=max(dp[i][j],dp[i-1][j-v[i][0]-v[i][1]]+v[i][0]*w[i][0]+v[i][1]*w[i][1]);
if(j>=v[i][0]+v[i][2])
dp[i][j]=max(dp[i][j],dp[i-1][j-v[i][0]-v[i][2]]+v[i][0]*w[i][0]+v[i][2]*w[i][2]);
if(j>=v[i][0]+v[i][1]+v[i][2])
dp[i][j]=max(dp[i][j],dp[i-1][j-v[i][0]-v[i][1]-v[i][2]]+v[i][0]*w[i][0]+v[i][1]*w[i][1]+v[i][2]*w[i][2]);
}
}
printf("%d\n",dp[k][n]);
return 0;
}