#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
//源码作者：华科不平凡
/*
解题思路：
01背包变体，相较于01背包问题的容积限制，这里以总钱数为限制，计算在一定钱数范围内的满意度 价格*权重。
比01背包麻烦的地方在于分组。
题中有附件必须有附件依赖的主件，且主件最多有两个附件，那么分组 可分为 只有主件、主件+附件1、主件+附件2、主件+附件1、2
dp[i][j]表示在奖金数j的范围内，取前i件物品的满意度
int a1 = price[i][0], a2 = weight[i][0];//主件
int b1 = price[i][1], b2 = weight[i][1];//附件1
int c1 = price[i][2], c2 = weight[i][2];//附件2
1.dp[i][j] = j >= a1 ? max(dp[i-1][j], dp[i-1][j-a1] + a2) : dp[i-1][j];//主件，如果钱能够覆盖主件，就取加入与不加入该主件的最大值；如果钱覆盖不了，就取不加入主件的值
2.dp[i][j] = j >= (a1+b1) ? max(dp[i][j],dp[i-1][j-a1-b1] + a2 + b2) : dp[i][j];//主件+附件1，关键点在于取最大值是dp[i][j]与加主件、附件的比较，因为如果能覆盖主件+附件，那么必
满足状态1，就应该继承状态1的dp[i][j]参与比较而非dp[i-1][j],后续状态3 4也是如此
3.dp[i][j] = j >= (a1+c1) ? max(dp[i][j],dp[i-1][j-a1-c1]+ a2 + c2) : dp[i][j];//主件+附件2
4.dp[i][j] = j >= (a1+b1+c1) ? max(dp[i][j],dp[i-1][j-a1-b1-c1] + a2 + b2 +c2) : dp[i][j];//主件+附件1+附件2
*/
int main() {
    int N,m;//N:总钱数，m:可购买物品的个数
    cin >> N >> m;

    N /= 10;//每件价格为10的整数倍，可进一步缩小dp
    vector<vector<int> > price(m+1,vector<int>(3,0));//价格
    vector<vector<int> > weight(m+1,vector<int>(3,0));//满意度
    int p,w,type;//分别表示物品价格、重要度、主/附件
    for(int i = 1; i <= m; ++i){
        cin >> p >> w >>type;
        p /= 10;//与总钱数保持一致
        w = p * w;//进一步变为满意度
        if(type == 0){//是主件
            price[i][0] = p;
            weight[i][0] = w;
        }else{//是附件
            if(price[type][1] == 0){//主件type的附件1
                price[type][1] = p;
                weight[type][1] = w;
            }else{//主件type的附件2
                price[type][2] = p;
                weight[type][2] = w;
            }
        }
    }
    //dp[i][j]表示恰好花费j元下买i件物品的最大满意度
    vector<vector<int> > dp(m+1,vector<int>(N+1,0));
   
    //分组，物品搭配(主件，主件+附件1，主件+附件2，主件+附件1+附件2)
    for(int i = 1; i <= m; i++){
        for(int j = 1; j <= N; j++){//其实可以加各判断price[i][0]是否为0，是0就跳过因为有附件那么price[i][0]在m件内必有0，因为附件算在主件的price[i][1] [1][2]内
            int a1 = price[i][0], a2 = weight[i][0];//主件
            int b1 = price[i][1], b2 = weight[i][1];//附件1
            int c1 = price[i][2], c2 = weight[i][2];//附件2
            dp[i][j] = j >= a1 ? max(dp[i-1][j], dp[i-1][j-a1] + a2) : dp[i-1][j];//主件
            dp[i][j] = j >= (a1+b1) ? max(dp[i][j],dp[i-1][j-a1-b1] + a2 + b2) : dp[i][j];//主件+附件1
            dp[i][j] = j >= (a1+c1) ? max(dp[i][j],dp[i-1][j-a1-c1]+ a2 + c2) : dp[i][j];//主件+附件2
            dp[i][j] = j >= (a1+b1+c1) ? max(dp[i][j],dp[i-1][j-a1-b1-c1] + a2 + b2 +c2) : dp[i][j];//主件+附件1+附件2
        }
    }
    cout << dp[m][N]*10 << endl;
}
// 64 位输出请用 printf("%lld")