#include<bits/stdc++.h>
using namespace std;
const int N=3201;
int v[N],q[N],p[N];
int dp[N][N];//只记主件 money=j,people=i
int fj[N][3];
int ma[N],top=0;
int main()
{
	//freopen("lock.in","r",stdin);
	//freopen("ans.out","w",stdout);
	int n,m;
	cin>>n>>m;
	n/=10;
	for(int i=1;i<=m;i++)
	{
		cin>>v[i]>>p[i]>>q[i];
		v[i]/=10;
		p[i]*=v[i];
		if(q[i]!=0) 
		{
			if(fj[q[i]][1]==0) fj[q[i]][1] = i;
			else fj[q[i]][2] = i;
		}										
		else
		ma[++top] = i;
	} 
//	for(int i=1;i<=m;i++) cout<<i<<" "<<p[i]<<endl;
	for(int i=1;i<=top;i++)																																														
			for(int j=1;j<=n;j++)
			{
				int now=ma[i];
				if(j>=v[now])
					dp[i][j] = max(dp[i-1][j],dp[i-1][j-v[now]]+p[now]);
				if(fj[now][1]!=0&&j>=v[now]+v[fj[now][1]])
				{
					dp[i][j] = max(dp[i][j],dp[i-1][j-v[now]-v[fj[now][1]]]+p[now]+p[fj[now][1]]);
				}

				if(fj[now][2]!=0&&j>=v[now]+v[fj[now][2]])
				{
					dp[i][j] = max(dp[i][j],dp[i-1][j-v[now]-v[fj[now][2]]]+p[now]+p[fj[now][2]]);
					dp[i][j] = max(dp[i][j],dp[i-1][j-v[now]-v[fj[now][2]]-v[fj[now][1]]]+p[now]+p[fj[now][2]]+v[fj[now][1]]);
				}
			}
	cout<<dp[top][n]*10;

}