#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define ll long long
using namespace std;
vector<int> w[105],v[105]; 
int n=0,m=0,a=0,b=0,c=0,g=0;
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>m;
	int dp[m+5][n+5];
	memset(dp,0,sizeof(dp));
	for(int i=1;i<=m;i++)
	{
		cin>>a>>b>>c;
		if(c==0)
		{
			g++;
			w[g].insert(w[g].begin(),a);
			v[g].insert(v[g].begin(),a*b);
			//w[g].pb(a);
			//v[g].pb(a*b);
		}
		else
		{
			w[c-(i-g)].pb(a);
			v[c-(i-g)].pb(a*b);	
		}	
	}
	for(int i=1;i<=g;i++)
	{
		//select=(int)w[i].size();
		for(int j=0;i<=n;j++)
		{
			if(w[i].size()==1)
			{
				if(j>=w[i][0])
				{
					dp[i+1][j]=max(dp[i+1][j],(dp[i+1][j-w[i][0]])+v[i][0]);
				}
				else
				{
					dp[i+1][j]=max(dp[i][j],dp[i+1][j]);
				}
			}
			
			
			
			if(w[i].size()==2)
			{
				if(j>=w[i][0])
				{
					dp[i+1][j]=max(dp[i+1][j],dp[i+1][j-w[i][0]]+v[i][0]);
				}
				else
				{
					dp[i+1][j]=max(dp[i][j],dp[i+1][j]);
				}
				
				if(j>=w[i][0]+w[i][1])
				{
					dp[i+1][j]=max(dp[i+1][j],dp[i+1][j-w[i][0]-w[i][1]]+v[i][0]+v[i][1]);
				}
				else
				{
					dp[i+1][j]=max(dp[i][j],dp[i+1][j]);
				}
			}
			
			
			
			if(w[i].size()==3)
			{
				if(j>=w[i][0])
				{
					dp[i+1][j]=max(dp[i+1][j],dp[i+1][j-w[i][0]]+v[i][0]);
				}
				else
				{
					dp[i+1][j]=max(dp[i][j],dp[i+1][j]);
				}
				
				if(j>=w[i][0]+w[i][1])
				{
					dp[i+1][j]=max(dp[i+1][j],dp[i+1][j-w[i][0]-w[i][1]]+v[i][0]+v[i][1]);
				}
				else
				{
					dp[i+1][j]=max(dp[i][j],dp[i+1][j]);
				}
				
				if(j>=w[i][0]+w[i][2])
				{
					dp[i+1][j]=max(dp[i+1][j],dp[i+1][j-w[i][0]-w[i][2]]+v[i][0]+v[i][2]);
				}
				else
				{
					dp[i+1][j]=max(dp[i][j],dp[i+1][j]);
				}
				
				if(j>=w[i][0]+w[i][1]+w[i][2])
				{
					dp[i+1][j]=max(dp[i+1][j],dp[i+1][j-w[i][0]-w[i][1]-w[i][2]]+v[i][0]+v[i][1]+v[i][2]);
				}
				else
				{
					dp[i+1][j]=max(dp[i][j],dp[i+1][j]);
				}
			}
		}
	}
	cout<<dp[g+1][n];
	return 0;
}