# N 总钱数
# m 希望购买的物品个数
#  从第 2 行到第 m+1 行，第 j 行给出了编号为 j-1 的物品的基本数据，每行有 3 个非负整数 v p q
# （其中 v 表示该物品的价格（ v<10000 ）， p 表示该物品的重要度（ 1 ~ 5 ）， q 表示该物品是主件还是附件。
# 如果 q=0 ，表示该物品为主件，如果 q>0 ，表示该物品为附件， q 是所属主件的编号）
# 输出描述：
#  输出一个正整数，为张强可以获得的最大的满意度。
# 800 2 0
# 400 5 1
# 300 5 1
# 400 3 0
# 500 2 0
# 将此问题等价为背包问题，购买分为：1、购买主件；2、购买主件 + 附件1；3、购买主件 + 附件2；4、购买主件 + 附件1 + 附件2
# 设 w[i][k] 表示，第i件物品的第k种购买情况的价格，k 取值 0,1,2,3 对应上面四种情况
# 设 v[i][k] 表示，第i件物品的第k种购买情况的满意度，k 取值同上
# 获取到输入的主件个数作为背包问题输入的物品个数，总钱数为背包容量
while True:
    try:
        n, m = map(int, input().split())
        primary = {}  # 存储主件信息
        annes = {}    # 存储附件信息
        for i in range(1,m + 1):
            x, y, z = map(int, input().split())
            if z == 0: # 主件标识，识别为主件
                primary[i] = [x, y]
            else:
                if z in annes:   # 第二个附件，加入
                    annes[z].append([x, y]) # 第二个附件，添加到已存在的附件列表里边即可
                else:
                    annes[z] = [[x, y]] # 第一个附件，附初始值 ；一个主件可能有1个或两个附件，故设计为二维数组形式
        # 获取主件的个数，作为物品个数
        m = len(primary)
        # 涉及状态转换数组 dp[][] ; dp[i][j] 表示在背包容量为j时，第i个物品放入背包后，背包存储的物品最大价值
        dp = [[0] * (n + 1) for _ in range(m + 1)]

        # 进行向背包问题的转换,附件问题处理： w[i][k],v[i][k]
        w, v = [[]] , [[]] # 存储等价抓换后的每个物品的 w[][]和 v[][]
        for key in primary:  # 遍历存储主件的字典
            w_temp, v_temp = [], []
            w_temp.append(primary[key][0]) # 1.主件key的重量
            v_temp.append(primary[key][0] * primary[key][1])  # 主件key的价值
            if key in annes:  # 该主键存在附件
                w_temp.append(w_temp[0] + annes[key][0][0])  # 2.主件 + 附件1 的重量
                v_temp.append(v_temp[0] + annes[key][0][0] * annes[key][0][1]) # 主件 + 附件1的价值
                if len(annes[key]) > 1: # 该主键存在两个附件
                    w_temp.append(w_temp[0] + annes[key][1][0]) # 主件 + 附件2 的重量
                    v_temp.append(v_temp[0] + annes[key][1][0] * annes[key][1][1]) # 主件 + 附件2 的价值
                    w_temp.append(w_temp[0] + annes[key][0][0] + annes[key][1][0]) # 主件 + 附件1 + 附件2的重量
                    v_temp.append(v_temp[0] + annes[key][0][0] * annes[key][0][1] + annes[key][1][0] * annes[key][1][1])
            w.append(w_temp)
            v.append(v_temp)

        # 进行典型背包问题的迭代
        for i in range(1, m + 1):        # 按物品个数进行循环
            for j in range(10, n + 1,10): # 背包容量是10的整数倍递增的
                max_i = dp[i - 1][j]
                for k in range(len(w[i])):
                    if j - w[i][k] >= 0:
                        max_i = max(max_i, dp[i-1][j - w[i][k]] + v[i][k])
                dp[i][j] = max_i
        print(dp[m][n])
    except:
        break