#include <bits/stdc++.h>
using namespace std;
int n,weight,v,p,q,f[50010]；
//定义结构体
struct Node{
	int zv,zj,fv1,fj1,fv2,fj2;
}a[50010];
int main(){
	cin>>weight>>n;
	for (int i=1;i<=n;i++){
		cin>>v>>p>>q;
		if (!q){
			a[i].zv=v;
			a[i].zj=v*p;
		}else{
			if (!a[q].fj1){
				a[q].fv1=v;
				a[q].fj1=v*p;
			}else{
				a[q].fv2=v;
				a[q].fj2=v*p;
			}
		}
	}
	for (int i=1;i<=n;i++){
		if (!a[i].zj)continue;
		for (int j=weight;j>=a[i].zv;j--){
			f[j]=max(f[j],f[j-a[i].zv]+a[i].zj);
			if (a[i].zv+a[i].fv1<=j)f[j]=max(f[j],f[j-a[i].zv-a[i].fv1]+a[i].zj+a[i].fj1);
			if (a[i].zv+a[i].fv2<=j)f[j]=max(f[j],f[j-a[i].zv-a[i].fv2]+a[i].zj+a[i].fj2);
			if (a[i].zv+a[i].fv1+a[i].fv2<=j)f[j]=max(f[j],f[j-a[i].zv-a[i].fv1-a[i].fv2]+a[i].zj+a[i].fj1+a[i].fj2);
		}
	}
	cout<<f[weight];
	return 0;
}