#include<bits/stdc++.h>
using namespace std;
int n,m,v[70][4],w[70][4],cnt[70],dp[32010];
int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
    	int cv,p,q;
    	cin>>cv>>p>>q;
    	if(q==0) w[i][1]=cv/10,v[i][1]=p*cv/10;
    	else w[q][++cnt[q]+1]=cv/10,cv,v[q][cnt[q]+1]=p*cv/10;
	}
	for(int i=1;i<=m;i++)
	{
		for(int j=n/10;j>=w[i][1]+w[i][2]+w[i][3];j--)
		{
			dp[j]=max({dp[j],dp[j-w[i][1]]+v[i][1],dp[j-w[i][1]-w[i][2]]+v[i][1]+v[i][2],dp[j-w[i][1]-w[i][3]]+v[i][1]+v[i][3],dp[j-w[i][1]-w[i][2]-w[i][3]]+v[i][1]+v[i][2]+v[i][3]});
		}
	}
	cout<<dp[n/10]*10;
    return 0;
}