#include<bits/stdc++.h>
#define maxn 500005
using namespace std;
struct zj
{
	int zxzyd;
	int jg;
	int zyd;
	bool fj1;
	int zyd1;
	int jg1;
	bool fj2;
	int zyd2;
	int jg2;
};
int dp[maxn],maxj;
zj st[maxn];
int top;
int main()
{
	int m;
	cin>>maxj>>m;
	for(int i=1;i<=m;i++)
	{
		int xi,yi,zi;
		cin>>xi>>yi>>zi;
		if(zi==0)	st[++top].jg=xi,st[top].zyd=xi*yi;
		else if(st[zi].fj1!=0)
		{
			st[zi].fj1=1;
			st[zi].jg1=xi;
			st[zi].zyd1=xi*yi;
			st[zi].zxzyd=min(st[zi].jg1,st[zi].jg);
		}
		else
		{
			st[zi].fj2=1;
			st[zi].jg2=xi;
			st[zi].zyd2=xi*yi;
			st[zi].zxzyd=min(st[zi].jg1,min(st[zi].jg2,st[zi].jg));
		}
		
	}
	for(int i=1;i<=top;i++)
	{
		for(int j=maxj;j>=st[i].zxzyd;j--)
		{
			if(st[i].fj1==0)	dp[j]=max(dp[j],dp[j-st[i].jg]+st[i].zyd);
			if(st[i].fj2==0)	dp[j]=max(dp[j],dp[j-st[i].jg1]+st[i].zyd1);
			if(st[i].fj2==1)	dp[j]=max(dp[j],dp[j-st[i].jg1]+st[i].zyd2);
		}
	}
	cout<<dp[maxj];
}