0分，错哪了，码风奇怪，请见谅

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef float fl;
typedef double dou;

const ll inf = 0x3f3f3f3f;
const ll mod = 1e9 + 7;

inline ll read()
{
	ll ans = 0;
	ll f = 1;
	char c = getchar();
	
	while( c < '0' || c > '9' )
	{
		if( c == '-' )
		{
			f = -1;
		}
		
		c = getchar();
	}
	
	while( c >= '0' && c <= '9' )
	{
		ans = ( ans << 3 ) + ( ans << 1 ) + ( c ^ 48 );
		c = getchar();
	}
	
	return ans * f;
}

inline void write( ll x )
{
	if( x > 9 )
	{
		write( x / 10 );
	}
	
	putchar( x % 10 + '0' );
}

int dp[32001] = {0};

struct main_thing
{
	int cnt;
	int va[2];
	int all[2];
	int val;
	int p;
}mt[32001];

int main()
{
	int i = 0;
	int j = 0;
	int n = 0;
	int m = 0;
	int v = 0;
	int p = 0;
	int q = 0;
	
	cin >> n >> m;
	
	for( i = 1 ; i <= m ; i++ )
	{
		cin >> v >> p >> q;
		
		if( q )
		{
			mt[q].va[++mt[q].cnt] = v;
			mt[q].all[mt[q].cnt] = v * p;
		}
		else
		{
			mt[i].p = v * p;
			mt[i].val = v;
		}
	}
	
	for( i = 1 ; i <= m ; i++ )
	{
		for( j = n ; j >= mt[i].val ; j-- )
		{
			if( j >= mt[i].val )
			{
				dp[j] = max( dp[j] , dp[j - mt[i].val] + mt[i].p );
			}
			
			if( j >= mt[i].val + mt[i].va[1] )
			{
				dp[j] = max( dp[j] , dp[j - mt[i].val - mt[i].va[1]] + mt[i].p + mt[i].all[1] );
			} 
			
			if( j >= mt[i].val + mt[i].va[2] )
			{
				dp[j] = max( dp[j] , dp[j - mt[i].val - mt[i].va[2]] + mt[i].p + mt[i].all[2] );
//				cout << mt[i].val + mt[i].va[2] << endl << i << endl << endl;
			}
			
			if( j >= mt[i].val + mt[i].va[1] + mt[i].va[2] )
			{
				dp[j] = max( dp[j] , dp[j - mt[i].val - mt[i].va[1] - mt[i].va[2]] + mt[i].p + mt[i].all[1] + mt[i].all[2] );
			}
			
//			cout << dp[n] << endl;
		}
	}
	
	cout << dp[n];
	
	return 0;
}