#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
/*
动态规划:
思路:总钱数N是10的倍数,除以10减少范围,且价格v除以10;根据附件标签q将主件、附件分别存储价格、总值。
*/
int main()
{
int N, m; // N 表示总钱数, m希望购买物品的个数
cin>>N>>m;
N /= 10; // 每件物品的价格都是10的整数倍,因此这里除以10,减少取值范围,结束时需要乘以10以还原。
vector<vector<int>> price(m+1, vector<int>(3, 0)); // 主键、附件价格
vector<vector<int>> sumValue(m+1, vector<int>(3, 0)); // 价格*重要度
vector<vector<int>> dp(m+1, vector<int>(N+1, 0)); //dp数组
for (int i = 1; i <= m; i++) {
int v, p, q; // v 表价格, p表示重要度, q表示主件还是附件(0表示主件,大于表示附件编号)
cin>>v>>p>>q;
v /= 10; // 所有价格都是10倍
p *= v; // 总值= 重要度*价格
if (q == 0) { // 主件
price[i][0] = v; //主件价格
sumValue[i][0] = p; //主件总值
} else if (q > 0) { // 附件
if (price[q][1] == 0) { //第一个附件
price[q][1] = v; //第一个附件价格
sumValue[q][1] = p; //第一个附件总值
} else {
price[q][2] = v; //第二个附件价格
sumValue[q][2] = p; //第二个附件总值
}
}
}
// 根据动态规划原则,求最大值通过分阶段决策,即分阶段求最大值,将所有阶段的最大值相加等于总值。
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= N; j++) {
// 必须足够的钱购买主件
// 主件最大总值
if (j >= price[i][0]) { //主件
//dp[i-1][j-price[i][0]] + sumValue[i][0] 表示当前的总值,dp[i-1][j]表示上一次的总值
dp[i][j] = max(dp[i - 1][j - price[i][0]] + sumValue[i][0], dp[i-1][j]); // 当前总值与上一次总值比较,取最大值
} else {
dp[i][j] = dp[i - 1][j]; // 上一次总值
}
//可以买主件 + 第一个附件
if (j >= price[i][0] + price[i][1]) {
dp[i][j] = max(dp[i - 1][j - price[i][0] - price[i][1]] + sumValue[i][0] + sumValue[i][1], dp[i][j]);
}
//可以买主件 + 第二个附件
if (j >= price[i][0] + price[i][2]) {
dp[i][j] = max(dp[i - 1][j - price[i][0] - price[i][2]] + sumValue[i][0] + sumValue[i][2], dp[i][j]);
}
//可以买主件 + 两个附件
if (j >= price[i][0] + price[i][1] + price[i][2]) {
dp[i][j] = max(dp[i - 1][j - price[i][0] - price[i][1] - price[i][2]] + sumValue[i][0] + sumValue[i][1] + sumValue[i][2], dp[i][j]);
}
}
}
cout << dp[m][N] * 10 << endl; //输出要乘回10倍
return 0;
}