#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <memory.h>
using namespace std;

int weii[65],vall[65],to[65];
int num,val[65][3210],numfu,limfu,weifu[65],valfu[65];
int f[65][3210];

int main(void)
{
	freopen("budgetb.in","r",stdin);
	freopen("budgetb.out","w",stdout);
	int i,j,k,lim,n,s,temp;
	cin>>lim>>n>>s;
	lim/=10;
	for (i=1;i<=n;i++)
	{
		cin>>weii[i]>>vall[i]>>to[i];
		vall[i]*=weii[i];
		weii[i]/=10;
	}
	for (i=1;i<=n;i++)
	{
		if (!to[i])
		{
			num++;
			for (j=weii[i];j<=lim;j++)
				val[num][j]=vall[i];
			numfu=0;
			limfu=lim-weii[i];
			for (j=1;j<=n;j++)
			{
				if (to[j]==i)
				{
					numfu++;
					weifu[numfu]=weii[j];
					valfu[numfu]=vall[j];
				}
			}
			memset(f,0,sizeof(f));
			for (j=1;j<=numfu;j++)
				for (k=0;k<=limfu;k++)
				{
					f[j][k]=f[j-1][k];
					temp=k-weifu[j];
					if (temp>=0)
						f[j][k]=max(f[j][k],f[j-1][temp]+valfu[j]);
				}
			/*f[numfu][XXX]*/
			for (j=weii[i],k=0;j<=lim;j++,k++)
				val[num][j]+=f[numfu][k];
		}
	}
	memset(f,0,sizeof(f));
	for (i=1;i<=num;i++)
		for (j=0;j<=lim;j++)
		{
			f[i][j]=f[i-1][j];
			for (k=0;k<j;k++)
				f[i][j]=max(f[i][j],f[i-1][k]+val[i][j-k]);
		}
	cout<<f[num][lim]<<endl;
	/* ans*10? */
	return(0);
}