#include<stdio.h>
main()
{
long int f[200001]={0};
long int v[61000][3]={0,0},p[60001][3]={0,0};
long int n,m,i,a,b,c,j;
scanf("%ld %ld",&n,&m);
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&a,&b,&c);
a=a/10;
if(c==0)c=i;
for(j=0;j<=2;j++)
{
if(v[c][j]==0)
{
v[c][j]=a;
p[c][j]=a*b;
break;
}
}
}
for(i=1;i<=m;i++)
{
if(v[i][0]!=0)
{
for(j=n/10;j>=v[i][0];j--)
{
if((j>=v[i][0])&&(f[j-v[i][0]]+p[i][0]>f[j])) f[j]=f[j-v[i][0]]+p[i][0];
if((j>=(v[i][0]+v[i][1]))&&(f[j-v[i][0]-v[i][1]]+p[i][0]+p[i][1]>f[j])) f[j]=f[j-v[i][0]-v[i][1]]+p[i][0]+p[i][1];
if((j>=(v[i][0]+v[i][2]))&&(f[j-v[i][0]-v[i][2]]+p[i][0]+p[i][2]>f[j])) f[j]=f[j-v[i][0]-v[i][1]]+p[i][0]+p[i][2];
if((j>=(v[i][0]+v[i][1]+v[i][2]))&&(f[j-v[i][0]-v[i][1]-v[i][2]]+p[i][0]+p[i][1]+p[i][2]>f[j])) f[j]=f[j-v[i][0]-v[i][1]-v[i][2]]+p[i][0]+p[i][1]+p[i][2];
}
}
}
printf("%ld",f[n/10]*10);
}