#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;
}