#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<set>
#include<stack>
#include<map>
#include<cmath>
using namespace std;
const int N = 63, inf = 0x3f3f3f3f;
typedef pair<int, int> PIR;
typedef long long ll;
PIR master[N];//存储主物品
vector<PIR>servent[N];//副物品
int f[32003];//这是个分组背包问题，因为每个副物品最多只有两个，所以当主物品被选择后，
//针对副物品就最多有四种选择，也就是每个组里最多只有四种选择。
int main()
{
int n, m;
cin >> m >> n;
for (int i = 1; i <= n; i++)
{
int v, p, q;
cin >> v >> p >> q;
if (!q)
master[i] = { v,v * p };
else
servent[q].push_back({ v,v * p });
}
for (int i = 1; i <= n; i++)//枚举物品
if (master[i].first)//为0说明这个主物品不存在或者存在但是价格为0
{
for (int j = m; j >= 0; j--)//枚举体积
{
auto& sv = servent[i];
for (int k = 0; k < 1 << servent[i].size(); k++)//二进制枚举方案
{
int v = master[i].first, w = master[i].second;//主物品必须选
for (int u = 0; u < servent[i].size(); u++)
if (k >> u & 1)//选择当前的副物品
{
v += sv[u].first;
w += sv[u].second;
}
if (j >= v)
f[j] = max(f[j], f[j - v] + w);
}
}
}
cout << f[m];
return 0;
}
