#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
int n,m,s,w[100][3],q[5000][3205]={0},answer=0;
vector<int>con[100];
int f[10000][2]={0},num=0,o;
void dfs(int x,int y,int z,int k);
int main()
{
	freopen ("budgetb.in","r",stdin);
	freopen ("budgetb.out","w",stdout);
	cin>>n>>m>>s;
	for (int i=1;i<=m;i++)
	{
		cin>>w[i][0]>>w[i][1]>>w[i][2];
		w[i][0]/=10;
		if (w[i][2]>0)
		{
			con[w[i][2]].push_back(i);
		}
		if (w[i][2]==0)
		{		
			f[++num][0]=w[i][0];
			f[num][1]=w[i][1]*w[i][0];
		}
	}
	for (o=1;o<=m;o++)
	{
		if (con[o].size()>0)
		{
			dfs(0,0,0,0);
		}
	}
	q[0][0]=0;
	for (int i=1;i<=num;i++)
	{
		for (int j=1;j<=n/10;j++)
		{
			if (j-f[i][0]>=0)
			{
				q[i][j]=max(q[i][j],q[i-1][j-f[i][0]]+f[i][1]);
				if (q[i][j]>answer)
					answer=q[i][j];
			}
		}
	}
	cout<<answer*10;
	return 0;
}

void dfs(int x,int y,int z,int k)
{
	if (x==con[o].size()&&k<=s)
	{
		if (y==0)
			return;
		f[++num][0]=y+w[o][0];
		f[num][1]=z+f[o][1];
		return;
	}
	for (int i=0;i<2;i++)
	{
		dfs(x+1,y+w[con[o][x]][0]*i,z+w[con[o][x]][1]*i*w[con[o][x]][0],k+i);
	}
}