#include <cstdio>
#include <string>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXM=33000;
const int MAXN=100;
const int MAXS=12;
int N,M,S,F[MAXM]={0},MF=0;
class MainFile
{
public:int child,value,price;
int cvalue[MAXS],cprice[MAXS];
}E[MAXN];

inline void init()
{
	scanf("%d %d %d\n",&M,&N,&S);
	M/=10;
	int tvv[MAXM]={0},
		tpp[MAXN]={0},
		tbb[MAXN]={0},
		tmf[MAXN]={0};
	for(int i=1;i<=N;i++)
	{
		scanf("%d %d %d\n",&tpp[i],&tvv[i],&tbb[i]);
		if(tbb[i]==0)
		{
			MF++;E[MF].value=tvv[i];tmf[i]=MF;
			E[MF].price=tpp[i]/10; E[MF].child=0;
		} 
	}	int tmp;
	for(int i=1;i<=N;i++)
	{
		if(!tbb[i]) continue;
		tmp=tmf[tbb[i]]; E[tmp].child++;
		E[tmp].cvalue[E[tmp].child]=tvv[i];
		E[tmp].cprice[E[tmp].child]=tpp[i]/10;
	}
	/*
	for(int i=1;i<=MF;i++)
	{
		printf("MainFile %d-->%d %d %d\n",i,E[i].value,E[i].price,E[i].child);
		for(int j=1;j<=E[i].child;j++)
			printf("---SubFile %d-->%d %d\n",j,E[i].cvalue[j],E[i].cprice[j]);
		printf("\n");
	}*/
}
inline int Max(int a,int b){return a>b?a:b;}
int NowMainFile=0,TotValue,TotPrice;

void dfs(int deep)
{
	if(deep==E[NowMainFile].child+1)
	{
		TotValue+=E[NowMainFile].value;
		TotPrice+=E[NowMainFile].price;
		for(int i=M;i>=TotPrice;i--)
			F[i]=Max(F[i],F[i-TotPrice]+TotPrice*TotValue);
		TotValue-=E[NowMainFile].value;
		TotPrice-=E[NowMainFile].price;
		return;
	}
	dfs(deep+1);
	TotValue+=E[NowMainFile].cvalue[deep];
	TotPrice+=E[NowMainFile].cprice[deep];
	dfs(deep+1);
	TotValue-=E[NowMainFile].cvalue[deep];
	TotPrice-=E[NowMainFile].cprice[deep];
}

inline void dp()
{
	for(int i=1;i<=MF;i++)
	{
		NowMainFile=i;
		TotValue=0,TotPrice=0;
		dfs(1);
	}
	printf("%d\n",F[M]*10);
}

int main()
{
	freopen("budgetb.in","r",stdin);
	freopen("budgetb.out","w",stdout);
	init(); dp();
	return 0;
}