#include <bits/stdc++.h>
using namespace std;
#define int long long
#define x first
#define y second

typedef pair<int, int> PII;
const int M = 3e5 + 2e4 + 5, N = 65;

int n, m, cnt = 0;
int v[N], w[N], f[N][M];
vector <PII> servent[N];

signed main()
{
	cin >> m >> n;
	for(int i = 1; i <= n; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		b = a * b;
		if(!c)
		{
			v[i] = a;
			w[i] = b;
		}
		else servent[c].push_back({a, b});
	}
	for(int i = 1; i <= n; i++)
	{
		int siz = servent[i].size();
		for(int k = 0; k < (1 << siz); k++)
		{
			int volume = 0, worth = 0;
			for(int j = 0; j < siz; j++)
			{
				if((k >> j) & 1)
				{
					volume += servent[i][j].x;
					worth += servent[i][j].y;
				}
			}
			volume += v[i], worth += w[i];
			for(int j = m; j >= volume; j--)
				f[i][j] = max({f[i][j], f[i - 1][j], f[i - 1][j - volume] + worth});
		}
	}
	cout << f[n][m] << "\n";
	return 0;
}``````