#include <cstdio>
#include <cstring>

using namespace std;

int n,m;

int f[41000];
int a[41000];

int v[70],w[70],q[70],s;

void init()
{
	scanf("%d%d%d",&n,&m,&s);
	
	for (int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&v[i],&w[i],&q[i]);
		w[i] *= v[i];
	}
}

void work()
{
	for (int i=1;i<=m;i++)
		if (q[i]==0)
		{
			for (int j=1;j<=v[i];j++)
				a[j]=0;
			for (int j=v[i];j<=n;j++)
				a[j]=f[j-v[i]]+w[i];
			for (int j=1;j<=m;j++)
				if (q[j]==i)
					for (int k=n;k>=v[i]+v[j];k--)
						if (a[k-v[j]]+w[j]>a[k])
							a[k]=a[k-v[j]]+w[j];
		    for (int j=v[i];j<=n;j++)
				if (a[j]>f[j])
					f[j]=a[j];
		}
}

int main()
{
	freopen("budgetb.in","r",stdin);
	freopen("budgetb.out","w",stdout);
	
	init();
	work();
	
	printf("%d\n",f[n]);
	
	fclose(stdin); fclose(stdout);
	
	return 0;
}