#include<stdio.h>
int dp[35005];
int max(int a,int b)、
{
	if(a<b) return b;
	return a;
} 
int flag[35005];
int main()
{
	int T,num,n[1005],v[1005];//钱   n个数   钱  重要
	int q[1005];//配件 
	scanf("%d%d",&T,&num);
	for(int i=1;i<=num;i++) scanf("%d%d%d",&n[i],&v[i],&q[i]);
	for(int i=1;i<=num;i++)
	{
		for(int j=T;j>=0;j--)
		{
			if(q[i]==0)				  // 主件 
			{
				if(j>=n[i]) dp[j]=max(dp[j],dp[j-n[i]]+n[i]*v[i]);
				flag[i]=114514;
			}
			else					  // 配件 
			{
				if(flag[q[i]]==114514)// 买过主件 
				{
					if(j>=n[i]) dp[j]=max(dp[j],dp[j-n[i]]+n[i]*v[i]);
				}
				else if( flag[q[i]]!=114514 )         // 没买主件 
				{
					if(j>=(n[q[i]]+n[i]))
					{
						dp[j]=max(dp[j],dp[j-n[q[i]]-n[i]]+n[i]*v[i]+n[q[i]]*v[q[i]]);
						flag[q[i]]=114514;
					} 
				}
			}
		}
	}
	printf("%d",dp[T]);
	return 0;
}