#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll V[100],W[100],Q[100];
ll dp[100][100];
vector <ll> A[100];
int main()
{
	ll n,m;
	scanf("%lld%lld",&m,&n);
	for (ll i = 1; i <= n; i ++)
	{
		scanf("%lld%lld%lld",&V[i],&W[i],&Q[i]);
		if (Q[i]) A[Q[i]].push_back(i);
		W[i] *= V[i];
	}
	for (ll i = 1; i <= n; i ++)
	{
		for (ll j = 1; j <= m; j ++)
		{
			dp[i][j] = dp[i - 1][j];
			if (j >= V[i] && !A[i].size()) dp[i][j] = max(dp[i - 1][j],dp[i - 1][j - V[i]] + W[i]);
			if (A[i].size() == 1 && j >= V[i] + V[A[i][0]]) dp[i][j] = max(dp[i - 1][j],max(dp[i - 1][j - V[i]] + W[i],dp[i - 2][j - V[i] - V[A[i][0]]] + W[i] + W[A[i][0]]));
			if (A[i].size() == 2 && (j >= V[i] + V[A[i][1]] || j >= V[i] + V[A[i][0]])) dp[i][j] = max(dp[i - 1][j],max(dp[i - 1][j - V[i] + W[i]],max(dp[i - 2][j - V[i] - V[A[i][0]]] + W[i] + W[A[i][0]],dp[i - 2][j - V[i] - V[A[i][1]]] + W[i] + W[A[i][1]]))) ;
			if (A[i].size() == 2 && j >= V[i] + V[A[i][0]] + V[A[i][1]]) dp[i][j] = max(dp[i - 1][j],max(dp[i - 1][j - V[i] + W[i]],max(dp[i - 2][j - V[i] - V[A[i][0]]] + W[i] + W[A[i][0]],max(dp[i - 2][j - V[i] - V[A[i][1]]] + W[i],dp[i - 3][j - V[i] - V[A[i][1]] - V[A[i][0]]] + W[i] + W[A[i][0]] + W[A[i][1]]))));
		}
	}
	printf("%lld",dp[n][m]);
	return 0;
}