题解 | #购物单# 动态规划，记忆化搜索+dfs

from functools import cache
from math import inf
import collections
n, m = map(int, input().split())
d = {}  # major下标对应主件的实际编号
sub = collections.defaultdict(list) # 每个主件编号对应附件 在minor中的下标 组成的数组
major = []  # 主件价格，重要度
minor = []  # 附件价格，重要度
for i in range(m):
    g = list(map(int, input().split()))
    if g[2] == 0:
        major.append([g[0], g[1]])
        d[len(major) - 1] = i + 1 # major -> i
    else:
        minor.append([g[0], g[1]])
        sub[g[2]].append(len(minor) - 1)    # i -> minor
# print(major, minor)
# print(d, sub)
@cache
def dfs(i, cost):   # major中，前i个在总费用cost下的最大满意度
    if cost < 0:
        return -inf
    if i < 0:
        return 0
    idx = d[i]
    ans = dfs(i - 1, cost)  # 不买第i件物品

    # 买第i件物品
    val = major[i][0] * major[i][1]
    cost -= major[i][0]
    sub_g = sub[idx]
    cd = [] # 第i件物品对应附件的所有情况，[附件总花费， 附件总满意度]
    tmp = [0, 0]    # cd的添加项
    def sub_dfs(j): # 代价是什么，附件的所有情况
        # print(j)
        nonlocal cd, tmp
        if j < 0:
            cd.append(tmp)
            return
        sub_dfs(j - 1)  # 不买第j个附件

        # 买第j个附件
        tmp = [tmp[0] + minor[sub_g[j]][0], tmp[1] + minor[sub_g[j]][0] * minor[sub_g[j]][1]]
        sub_dfs(j - 1)
        tmp = [tmp[0] - minor[sub_g[j]][0], tmp[1] - minor[sub_g[j]][0] * minor[sub_g[j]][1]] # 恢复现场
        return
    sub_dfs(len(sub_g) - 1)
    # print(i, cd, sub_g)
    for c in cd:    # 第i个主件和对应附件的所有买入情况，取最大满意度
        ans = max(ans, dfs(i - 1, cost - c[0]) + val + c[1])
    return ans


ans = dfs(len(major) - 1, n)
print(ans)