#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>=v[i];j-=10)
					{
						if(j>=an)
						dp[j]=max(dp[j],dp[j-an]+av);
						if(j>=v[i])
						dp[j]=max(dp[j],dp[j-v[i]]+vv[i]);
					}
				}
				else if(bagvv[i].size()==2)
				{
					int av0=vv[i]+bagvv[i][0],an0=v[i]+bagv[i][0];
					int av1=vv[i]+bagvv[i][1],an1=v[i]+bagv[i][1];
					int av01=vv[i]+bagvv[i][0]+bagvv[i][1],an01=v[i]+bagv[i][0]+bagv[i][1];
					for(int j=n;j>=v[i];j-=10)
					{
						if(j>=v[i])
						dp[j]=max(dp[j],dp[j-v[i]]+vv[i]);
						if(j>=an0)
						dp[j]=max(dp[j],dp[j-an0]+av0);
						if(j>=an1)
						dp[j]=max(dp[j],dp[j-an1]+av1);
						if(j>=an01)
						dp[j]=max(dp[j],dp[j-an01]+av01);
					}
				}
				else
				{
				for(int j=n;j>=v[i];j-=10)
				dp[j]=max(dp[j],dp[j-v[i]]+vv[i]);
				}
	}
	cout<<dp[n];
}