#include <iostream>
#include <fstream>

using namespace std;

struct Thing
{
	int v,p,vc[11],pc[11];

	Thing()
	{
		for(int i=0;i<=10;i++)
			vc[i]=pc[i]=0;
		v=p=0;
	}
}thing[61];

int n,m,f[3201],cnt[61],c=0,s;

int main()
{
	freopen("budgetb.in","r",stdin);
	freopen("budgetb.out","w",stdout);
	cin>>n>>m>>s;
	n/=10;
	int v,p,q;
	for(int i=1;i<=m;i++)
	{
		cin>>v>>p>>q;
		v/=10;
		if(!q)
		{
			thing[++c].v=v;
			thing[c].p=p;
		}
		else
		{
			thing[q].vc[cnt[q]]=v;
			thing[q].pc[cnt[q]++]=p;
		}
	}

//	for(int i=1;i<=c;i++)
//	{
//		cout<<thing[i].v<<" "<<thing[i].p<<" "<<thing[i].pc[0]<<" "<<thing[i].vc[0]<<" "<<thing[i].pc[1]<<" "<<thing[i].vc[1]<<endl;
//	}

	for(int i=1;i<=c;i++)
	{
		for(int v=n;v>=thing[i].v;v--)
		{
			int temp=0,Max=0,t2,t3,t4;
			if(v-thing[i].v>=0)
			{
				Max=f[v-thing[i].v]+thing[i].v*thing[i].p;
				for(int k=1;k<(1<<cnt[i]);k++)
				{
					t2=t3=0;
					for(int temp=k,cc=cnt[i];temp;temp=temp>>1,cc--)
					{
						t2+=thing[i].vc[cc]*(temp&1);
						t3+=thing[i].pc[cc]*(temp&1);
					}
					if(t2>v)continue;
					if((t4=f[v-t2]+t2*t3)>Max)Max=t4;
				}
			}
			f[v]=max(f[v],Max);
		}
	}
	
	cout<<f[n]*10<<endl;

	return 0;
}