#感觉办法有点笨，有大佬会更好的吗

#include<iostream>
#include<vector>
using namespace std;
int n,m;
struct f
{
	int v;
	int p;
	int q;
	vector<f> ch;
};
f a[61]; 
int dp[32001];
int main()
{
	cin >> n >> m;
	for(int i=1;i<=m;i++)
	{
		cin >> a[i].v >> a[i].p >> a[i].q;
		if(a[i].q!=0)
		{
			a[a[i].q].ch.push_back(a[i]);
		}
	}
	for(int i=1;i<=m;i++)
	{
		for(int j=n;j>=0;j--)
		{
			if(a[i].q==0)
			{
				if(a[i].ch.size()==0)
				{
					if(j-a[i].v>=0)
					{
						dp[j]=max(dp[j],dp[j-a[i].v]+a[i].v*a[i].p);
					}
				}
				else if(a[i].ch.size()==1)
				{
					if(j-a[i].v>=0)
					{
						dp[j]=max(dp[j],dp[j-a[i].v]+a[i].v*a[i].p);	
					}
					if(j-a[i].v-a[i].ch[0].v>=0)
					{
						dp[j]=max(dp[j],dp[j-a[i].v-a[i].ch[0].v]+a[i].v*a[i].p+a[i].ch[0].v*a[i].ch[0].p);
					}	
				}
				else
				{
					if(j-a[i].v>=0)
					{
						dp[j]=max(dp[j],dp[j-a[i].v]+a[i].v*a[i].p);
					}
					if(j-a[i].v-a[i].ch[0].v>=0)
					{
						dp[j]=max(dp[j],dp[j-a[i].v-a[i].ch[0].v]+a[i].v*a[i].p+a[i].ch[0].v*a[i].ch[0].p);	
					}
					if(j-a[i].v-a[i].ch[1].v>=0)
					{
						dp[j]=max(dp[j],dp[j-a[i].v-a[i].ch[1].v]+a[i].v*a[i].p+a[i].ch[1].v*a[i].ch[1].p);	
					}
					if(j-a[i].v-a[i].ch[0].v-a[i].ch[1].v>=0)
					{
						dp[j]=max(dp[j],dp[j-a[i].v-a[i].ch[0].v-a[i].ch[1].v]+a[i].v*a[i].p+a[i].ch[0].v*a[i].ch[0].p+a[i].ch[1].v*a[i].ch[1].p);
					}	
				} 
			}
		}
	}
	cout << dp[n];
	return 0;
}