#include<iostream>
using namespace std;
int thing[61][2],thing_f[61][2][2],i=1,g[3201],v[60],v_f[61][2];
main()
{
int n,m;
cin>>n>>m;
memset(g,0,sizeof(g));
memset(thing,0,sizeof(thing));
memset(thing_f,0,sizeof(thing_f));
for(int k=0;k<m;k++)
{
int x,y,z;
cin>>x>>y>>z;
if(z==0)
{
thing[i][0]=x;
thing[i][1]=y;
i++;
}
else
{
if(thing_f[z][0][0])
{thing_f[z][1][0]=x;thing_f[z][1][1]=y;}
else {thing_f[z][0][0]=x;thing_f[z][0][1]=y;}
}
}
memset(v_f,0,sizeof(v_f));
for(int k=1;k<=i;k++)
{
v[k]=thing[k][0]*thing[k][1];
v_f[k][0]=thing_f[k][0][1]*thing_f[k][0][0];
v_f[k][1]=thing_f[k][1][1]*thing_f[k][1][0];
}
for(int k=1;k<=i;k++)
{
thing[k][0]/=10;
thing_f[k][0][0]/=10;
thing_f[k][1][0]/=10;
}
n/=10;
for(int k=1;k<=i;k++)
for(int j=n;j>0;j--)
{
if(j>thing[k][0]) g[j]=max(g[j],g[j-thing[k][0]]+v[k]);
if(j>thing[k][0]+thing_f[k][0][0]&&thing_f[k][0][0])
g[j]=max(g[j],g[j-thing[k][0]-thing_f[k][0][0]]+v[k]+v_f[k][0]);
if(j>thing[k][0]+thing_f[k][1][0]&&thing_f[k][1][0])
g[j]=max(g[j],g[j-thing[k][0]-thing_f[k][1][0]]+v[k]+v_f[k][1]);
if(j>thing[k][0]+thing_f[k][0][0]+thing_f[k][1][0]&&thing_f[k][1][0]&&thing_f[k][0][0])
g[j]=max(g[j],g[j-thing[k][0]-thing_f[k][0][0]-thing_f[k][1][0]]+v[k]+v_f[k][0]+v_f[k][1]);
}
cout<<g[n];
}