题目说了商品价格为10的倍数，动态规划数组dp的行数=商品数目，dp列数=总钱数，为了减少dp数组的列维度，将总钱数m整除10（dp数组列维度便缩小10倍），总钱数小了10倍再把每件商品价格也缩小10倍，购买方案就会和原来不变。注意：每件商品满意度在存储时仍记录原价的计算结果，即商品满意度=商品原价*商品重要程度

一、动态规划数组dp[i][j]：

含义：总钱数为j，遍历到第i件商品时，所能买到的最大满意度值

维度：N行m列，N为商品总数目，m为总钱数

状态转移：dp[i][j] = max(dp[i-1][j], dp[i-1][j-Price[i]]+Weight[i])，当总钱数j>=商品i价格Price[i]时

以遍历到上一件商品i-1为起点，dp[i-1][j]没有选择购入接下来的产品i，总钱数j保留，获取记录的满意度值dp[i-1][j]；dp[i-1][j-Price[i]]选择购入接下来的i产品，总钱数j减去商品价格，对获取到的满意度记录值dp[i-1][j-Price[i]] 再加上商品i的满意度Weight[i]

优化数组dp

1、二维缩小为一维：二维dp数组第i行总是用到第i-1行数据，可以每次只保留上一行数据留给下次遍历使用，由原来的二维dp[i][j]变成只记录一行（每次遍历前的上一行i-1）数据的一维dp[j]

2、对总钱数j进行倒序遍历：优化后的一维dp只保留上次的行记录值，新的状态转移中 dp[j] = max(dp[j], dp[j-Pi]+Wi)，索引 j的值总要依赖更小索引 j-Pi的记录值。当 j从大到小倒序遍历时，由于优化后的一维dp只保留上次的行记录值，比索引 j小的其他记录值还是上次的行记录值；但是当 j从小到大正序遍历时，会不断更新一维dp记录值，随着索引 j不断增大，用到的更小索引 j-Pi已经不是上次的行记录值，而是刚刚才更新过的新值（上次的行记录值已被覆盖）

二、更新dp数组的条件

当前总钱数 j 大于等于待购买商品总价时，更新dp数组

附件不能单独购买，所以遍历时只看主件。一个主件没有附件时，只考虑max（不买，买主件），有附件时：

1、有1个附件：当主件+附件总价格 <= 总钱数j，dp[j] = max（不买，买主件，买主件+附件）

2、有2个附件：

• 当主件+附件1总价格 <= 总钱数j，dp[j] = max（不买，买主件，买主件+附件1）；
• 当主件+附件2总价格 <= 总钱数j，dp[j] = max（不买，买主件，买主件+附件2）；
• 当主件+附件1总价格+附件2总价格 <= 总钱数j，dp[j] = max（不买，买主件，买主件+附件1，买主件+附件2，买主件+附件1+附件2）

class Good:
    def __init__(self, id, price, weight, belong) -> None:
        self.id = id  # 商品编号
        self.price = price  # 商品价格
        self.weight = weight  # 商品满意度：价格*重要度
        self.belong = belong  # 商品所属
        self.attach = []  # 商品附件

    def add_attach(self, good):
        self.attach.append(good)

while True:
    try:
        m, N = list(map(int, input().split(" ")))
        # 1、dp数组长度为总钱数，将商品价格与总钱数同比缩小10倍，缩小dp长度
        # 2、dp由2维减为1维度，实际只记录：遍历原2维数组时当前行的上一行
        m //= 10
        dp = [0 for _ in range(m + 1)]  # 总钱数为0,1,2...m
        goods = [None, ]  # 跳过索引0，从索引1开始
        for i in range(1, N + 1):
            p, w, b = list(map(int, input().split(" ")))
            good = Good(i, p // 10, w * p, b)  # 题目说商品价格为10的整数倍，这里对商品单价//10
            goods.append(good)
        # ------------- 遍历商品，将所有附件添加到对应主件的attach中
        for good in goods[1:]:  
            if good.belong != 0:  # 该商品为附件，good.belong为其主件的编号
                goods[good.belong].add_attach(good)
        # ------------- 遍历商品中的主件，更新dp数组
        for good in goods[1:]:
            if good.belong == 0:  # 遍历主件
                for j in reversed(range(m + 1)):  # 对一维dp的索引j进行倒序遍历，避免上次记录值被覆盖
                    if j >= good.price:
                        # 为dp[j]赋初值：max(不买, 主)
                        dp[j] = max(dp[j], dp[j - good.price] + good.weight)
                        # 根据主件拥有附件的个数，再更新dp[j]记录值
                        if len(good.attach) == 0:
                            continue
                        elif len(good.attach) == 1:
                            attach1 = good.attach[0]
                            # max(不买, 主, 主+附1)
                            if j >= good.price + attach1.price:  
                                dp[j] = max(
                                    dp[j],
                                    dp[j-good.price-attach1.price] + good.weight + attach1.weight,
                                )
                        elif len(good.attach) == 2:
                            attach1 = good.attach[0]
                            attach2 = good.attach[1]
                            # a = max(不买, 主, 主+附1)
                            if (j >= good.price + attach1.price):  
                                dp[j] = max(
                                    dp[j],
                                    dp[j-good.price-attach1.price] + good.weight + attach1.weight,
                                )
                            # b = max(a, 主+附2)
                            if (j >= good.price + attach2.price):  
                                dp[j] = max(
                                    dp[j],
                                    dp[j-good.price-attach2.price] + good.weight + attach2.weight,
                                )
                            # max(b, 主+附1+附2)
                            if (j >= good.price + attach1.price + attach2.price):  
                                dp[j] = max(
                                    dp[j],
                                    dp[j-good.price-attach1.price-attach2.price] + good.weight + \
                                        attach1.weight + attach2.weight,
                                )
                    else:
                        break
        print(dp[m])
    except:
        break