#include<stdio.h>
//n是钱，m是物品数
int d[30001][26],jg[26],jz[26],cong[26];
int max(int a,int b)
{
if(a>b) return a;
return b;
}
int main()
{
int n,m,i,j;
scanf("%d %d",&n,&m);
for(i=1;i<=m;i++)
{
scanf("%d %d %d",&jg[i],&jz[i],&cong[i]);
}
for(i=0;i<=n;i++)
{
d[0][i]=0;
d[i][0]=0;
}
for(i=1;i<=m;i++)
{
for(j=n;j>=1;j--)
{
if((jg[i]<=j)&&(cong[i]==0))
d[i][j]=max(d[i-1][j],d[i-1][j-jg[i]]+jz[i]*jg[i]);
else if((jg[i]<=j)&&(cong[i]!=0))
{
if(d[cong[i]][j]>d[cong[i]-1][j])
{
d[i][j]=max(d[i-1][j],d[i-1][j-jg[i]]+jz[i]*jg[i]);
}
else d[i][j]=d[i-1][j];
}
else
d[i][j]=d[i-1][j];
}
}
printf("%d",d[m][n]);
}