/*
#include <fstream>
#include <cstdlib>
#include <cstdio>
using namespace std;

struct 
{
	int v,w,l,r;
}a[61];
int n,m,s;
int p[61]={0};
int f[61][3201]={0};
int main()
{
	ifstream in("budgetb.in");
	ofstream out("budgetb.out");
	in>>n>>m>>s;
	n/=10;
	for(int i=1;i<=m;i++) for(int j=0;j<=n;j++) f[i][j]=-1;
	for(int i=0;i<=m;i++){ a[i].l=-1; a[i].r=-1;}
	a[0].w=0;
	for(int i=1;i<=m;i++)
	{
		int b,c,d;
		in>>b>>c>>d;
		b/=10;
		a[i].v=b;
		a[i].w=b*c;
		if(a[d].l=-1) a[d].l=i;
		else a[p[q]].r=i;
		p[q]=i;
	}
	for(int i=1;i<=m;i++)
	{
		if(a[i].l==-1 && a[i].r==-1)
			for(j=0;j<=n;j++)
			{
				if(j>=a[i].v)  f[i][j]=a[i].w;
				else f[i][j]=0;
			}
	}
	trdp(1,n);
	return 0;
}
*/
//  看来最多也就写个建树了，再好好看看吧 唉。。。。  50%  我来了



#include <fstream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
using namespace std;
int main()
{
	ifstream in("budgetb.in");
	ofstream out("budgetb.out");
	int n,m,s;
	int a[61][4]={0},b[61][4]={0};
	int f[32001]={0};
	in>>n>>m>>s;
	for(int i=1;i<=m;i++)
	{
		int v,p,q;
		in>>v>>p>>q;
		if(q==0)
		{
			a[i][0]=v;
			b[i][0]=p;
		}else
		{
			if(a[q][1]==0)
			{
				a[q][1]=v;
				b[q][1]=p;
			}else
			{
				a[q][2]=v;
				b[q][2]=p;
			}
		}
	}
	for(int i=1;i<=m;i++)
	{
		if(a[i][0]!=0)
		{
			for(int j=n;j>=1;j--)
			{
				int a1,a2,a3,a4;
				a1=j-a[i][0];
				a2=j-a[i][0]-a[i][1];
				a3=j-a[i][0]-a[i][1]-a[i][2];
				a4=j-a[i][0]-a[i][2];
				if(a1>=0) f[j]=max(f[j],f[a1]+b[i][0]*a[i][0]);
				if(a2>=0) f[j]=max(f[j],f[a2]+b[i][0]*a[i][0]+b[i][1]*a[i][1]);
				if(a3>=0) f[j]=max(f[j],f[a3]+b[i][0]*a[i][0]+b[i][1]*a[i][1]+b[i][2]*a[i][2]);
				if(a4>=0) f[j]=max(f[j],f[a4]+b[i][0]*a[i][0]+b[i][2]*a[i][2]);
			}
		}
	}
	out<<f[n]<<endl;
	return 0;
}