题解 | #购物单# AI给出的答案

def max_satisfaction(N, m, items):
    # 初始化dp数组，表示每个容量下的最大满意度
    dp = [0] * (N + 1)
    
    # 存储主件和附件的关系
    main_items = [[] for _ in range(m + 1)]  # 用来存储每个主件和它的附件列表
    for i in range(m):
        v, p, q = items[i]
        if q == 0:  # 主件
            main_items[i + 1].insert(0,(v, p))  # 把主件信息放进去
        else:  # 附件
            main_items[q].append((v, p))  # 将附件放到主件对应的列表中

    # 遍历每个主件，处理主件和其附件的组合
    for i in range(1, m + 1):
        if not main_items[i]:  # 如果该主件不存在，跳过
            continue
        
        # 拿到该主件和它的附件
        group = main_items[i]
        v0, p0 = group[0]  # 主件的价格和重要度
        v0p0 = v0 * p0  # 主件的满意度

        # 枚举背包容量
        for j in range(N, v0 - 1, -1):  # 从后往前更新DP，避免重复计算
            # 只选主件
            dp[j] = max(dp[j], dp[j - v0] + v0p0)
            
            # 选主件和一个附件1
            if len(group) >= 2:
                v1, p1 = group[1]
                if j >= v0 + v1:
                    dp[j] = max(dp[j], dp[j - v0 - v1] + v0p0 + v1 * p1)
            
            # 选主件和附件2
            if len(group) >= 3:
                v2, p2 = group[2]
                if j >= v0 + v2:
                    dp[j] = max(dp[j], dp[j - v0 - v2] + v0p0 + v2 * p2)

            # 选主件和两个附件
            if len(group) == 3:
                v1, p1 = group[1]
                v2, p2 = group[2]
                if j >= v0 + v1 + v2:
                    dp[j] = max(dp[j], dp[j - v0 - v1 - v2] + v0p0 + v1 * p1 + v2 * p2)

    return dp[N]


# 输入
N, m = map(int, input().split())
items = [tuple(map(int, input().split())) for _ in range(m)]

# 计算最大满意度
print(max_satisfaction(N, m, items))