#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int a[110000],w[110000],b[110][110],top[110];
int f[1100000];
int n,v;
int ans=0;
int main()
{
	freopen("budget.in","r",stdin);
	freopen("budget.out","w",stdout);
	cin>>v>>n;
	v/=10;
	int p;
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d%d",&w[i],&a[i],&p);
		w[i]/=10;
		a[i]*=w[i];
		if(p!=0)
		{
			b[p][++top[p]]=i;
			top[i]=-1;
		}
	}
	for(int i=1;i<=n;i++)
	{
		if(top[i]!=-1)
		{
			for(int j=v;j>=w[i];j--)
			{
				if(f[j]<f[j-w[i]]+a[i])
				{
					f[j]=f[j-w[i]]+a[i];
				}
				if(j-w[i]-w[b[i][1]]>=0&&f[j]<f[j-w[i]-w[b[i][1]]]+a[i]+a[b[i][1]])
				{
					f[j]=f[j-w[i]-w[b[i][1]]]+a[i]+a[b[i][1]];
				}
				if(top[i]==2&&j-w[i]-w[b[i][2]]>=0)
				{
					if(f[j]<f[j-w[i]-w[b[i][2]]]+a[i]+a[b[i][2]])
					{
						f[j]=f[j-w[i]-w[b[i][2]]]+a[i]+a[b[i][2]];
					}
					if(j-w[i]-w[b[i][1]]-w[b[i][2]]>=0)
					{
						if(f[j]<f[j-w[i]-w[b[i][1]]-w[b[i][2]]]+a[i]+a[b[i][1]]+a[b[i][2]])
						{
							f[j]=f[j-w[i]-w[b[i][1]]-w[b[i][2]]]+a[i]+a[b[i][1]]+a[b[i][2]];
						}
					}
				}
				if(f[j]>ans)
				{
					ans=f[j];
				}
			}
		}
	}
	cout<<ans*10<<endl;
	return 0;
}