先声明本人也是向大佬学习的，思路是按大佬的走的。
（链接：https://blog.nowcoder.net/n/82b5f014a8654c8b8dbff4fe4fa727bd?f=comment）

本题考的是动态规划，就是0-1背包问题，上述的博主说的非常详细了，大家多去参考上述博主的。
这里对自己做题的时候一些难点做点记录。
首先就是主附件的问题，他可能是主件附件按顺序出，也可能是附件先出，这时要分三种情况做记录，（1、第一个出的就是主件，则直接放进序列里。2、第一个附件先出，则同时把主件找出来，两个都放进序列里。3、第二个附件出来了，因为说明前面已经有第一个附件的情况了，所以直接放进序列里，但注意放进去的除了是主件+附件2的情况，还有主件+附件1+附件2的情况）这时在附件对应的位置上会有空序列，本人这里是继续做循环把空序列删掉，但根据博主的字典用法似乎更方便，各位可以自行选择。最后就是0-1背包问题的常规解法了，根据动态规划，找到最后一个点的值，就是我们要找的值（注意有附件时，dp[i][j]还要和自身做对比，有可能和单独主件的比较或者是和主件+附件1的比较比主件+附件1+附件2更好，此时应取前者，所以还要和自身比）。

while True:
    try:
        n, m = [int(x) for x in input().split()]
        n = n // 10

        v = [0] * m
        p = [0] * m
        q = [0] * m
        num1 = 0

        for i in range(m):
            v[i], p[i], q[i] = [int(x) for x in input().split()]
            v[i] = v[i] // 10

        value = [[] for _ in range(m+1)]
        significance = [[] for _ in range(m+1)]

        for i in range(m):
            if(q[i] == 0):                                          #主件
                value[i].append(v[i])
                significance[i].append(v[i]*p[i])
            else:
                if(len(value[q[i]-1]) == 0):                            #一开始只有附件的记录，把主件也记录进去
                    value[q[i]-1].append(v[q[i] - 1])
                    significance[q[i]-1].append(v[q[i] - 1]*p[q[i]-1])
                    value[q[i]-1].append(v[i]+v[q[i]-1])
                    significance[q[i]-1].append(v[i]*p[i]+v[q[i]-1]*p[q[i]-1])
                elif(len(value[q[i]-1]) == 1):                          #主件加第一个附件
                    value[q[i]-1].append(v[i]+v[q[i]-1])
                    significance[q[i]-1].append(v[i]*p[i]+v[q[i]-1]*p[q[i]-1])
                else:
                    value[q[i]-1].append(v[i]+v[q[i]-1])                #主件加第二个附件
                    significance[q[i]-1].append(v[i]*p[i]+v[q[i]-1]*p[q[i]-1])
                    value[q[i]-1].append(v[i]+value[q[i]-1][1])         #主件加第一个和第二个附件
                    significance[q[i]-1].append(v[i]*p[i]+significance[q[i]-1][1])

        num1 = 0

        for i in range(len(value)):
            if(value[i] == []):
                num1 += 1

        for i in range(num1):
            value.remove([])
            significance.remove([])

        dp = [[0 for _ in range(n+1)] for _ in range(len(value)+1)]

        for i in range(1,len(value)+1):
            for j in range(1,n+1):
                for k in range(len(value[i-1])):
                    if(value[i-1][k] > j):
                        dp[i][j] = max(dp[i-1][j], dp[i][j])
                    else:
                        dp[i][j] = max(dp[i][j], dp[i-1][j], dp[i-1][j - value[i-1][k]]+significance[i-1][k])

        print(dp[-1][-1]*10)
    except:
        break