#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,m;
	cin>>n>>m;
	vector<int> vv(m+1),v(m+1);
	vector<int> dp(n+1);
	vector<vector<int>> bagvv(m+1),bagv(m+1);
	int o=1;
	for(int i=0;i<m;i++)
	{
		int p,y,k0;
		cin>>y>>p>>k0;
		if(k0!=0)
		{
			bagv[k0].push_back(y);
			bagvv[k0].push_back(y*p);
		}
		else
		{
			v[o]=y;
			vv[o]=y*p;
			o++;
		}
	}
	for(int i=1;i<o;i++)
	{
				if(bagvv[i].size()==1)
				{
					int av=vv[i]+bagvv[i][0],an=v[i]+bagv[i][0];
					for(int j=n;j>=an;j--)
					dp[j]=max(dp[j],dp[j-an]+av);
				}
				else if(bagvv[i].size()==2)
				{
					int av=vv[i]+bagvv[i][0],an=v[i]+bagv[i][0];
					for(int j=n;j>=an;j--)
					dp[j]=max(dp[j],dp[j-an]+av);
					av=vv[i]+bagvv[i][1];
					an=v[i]+bagv[i][1];
					for(int j=n;j>=an;j--)
					dp[j]=max(dp[j],dp[j-an]+av);
					av=vv[i]+bagvv[i][0]+bagvv[i][1];
					an=v[i]+bagv[i][0]+bagv[i][1];
					for(int j=n;j>=an;j--)
					dp[j]=max(dp[j],dp[j-an]+av);
				}
				for(int j=n;j>=v[i];j--)
				dp[j]=max(dp[j],dp[j-v[i]]+vv[i]);
	}
	cout<<dp[n];
}