#include<stdio.h>
int max(int a,int b);
int main()
{int i=0,j=0,n=0,m=0,tv=0,tq=0,tp=0,cntm=0,cnts=0;
scanf("%d %d",&m,&n);//m和n和题目是反的。 
int mainw[1+n];
int mainv[1+n];
int cntsides[1+n];
int sidew[1+n][2];//第二维0表示第一个附件，1表示第二个附件。
int sidev[1+n][2];
int dp[1+m];
for(i=0;i<=n;i++)
{
	mainw[i]=0;//主件的代价。 
	mainv[i]=0;//主件的价值。 
	cntsides[i]=0;//主件的附件数量。 
	for(j=0;j<=1;j++)
	{
		sidew[i][j]=0;//附件的代价。
		sidev[i][j]=0;//附件的价值。
	}
}
for(i=0;i<n;i++)
{
	scanf("%d %d %d",&tv,&tp,&tq);
	if(tq==0)
	{
		cntm++;
		mainw[cntm]=tv;
		mainv[cntm]=tp*tv;
	}
	else
	{
		sidew[tq][cntsides[tq]]=tv;
		sidev[tq][cntsides[tq]]=tp*tv;
		cntsides[tq]++;
	}
}
for(i=0;i<=m;i++){dp[i]=0;}
i=1;
while(mainv[i]!=0)
{
	for(j=m;j>0;j--)
	{
		if(j>=mainw[i]){dp[j]=max(mainv[i]+dp[j-mainw[i]],dp[j]);}
		if(cntsides[i]>0&&j>=sidew[i][0]+mainw[i])
		{
			dp[j]=max(sidev[i][0]+mainv[i]+dp[j-mainw[i]-sidew[i][0]],dp[j]);
		}
		if(cntsides[i]>1&&j>=sidew[i][1]+mainw[i])
		{
			dp[j]=max(dp[j],sidev[i][1]+mainv[i]+dp[j-mainw[i]-sidew[i][1]]);
		}
		if(cntsides[i]>1&&j>=sidew[i][0]+sidew[i][1]+mainw[i])
		{
			dp[j]=max(sidev[i][0]+sidev[i][1]+mainv[i]+dp[j-mainw[i]-sidew[i][1]-sidew[i][0]],dp[j]);
		}
    }
    i++;
}
printf("%d",dp[m]);
return 0;
}
int max(int a,int b)
{
	if(b>a){return b;}
	return a;
}