n, m = map(int, input().split())	#n表示钱，m表示数量
v = [0] * (m + 1)
w = [0] * (m + 1)
q = [0] * (m + 1)	#这三个里面是列表[0],[0],[0],[0],[0],[0],[0](m+1个)

for i in range(1, m + 1):
    v[i], w[i], q[i] = map(int, input().split()) 	#输入每个商品的价格，重要度，和从属关系

goods = [[] for _ in range(m + 1)]	#创建从属关系列表

for i in range(1, m + 1):
    if q[i] != 0:
        goods[q[i]].append(i)		#将有从属关系的表示i的附件的加入gppds[i]中

dp = [0] * (n + 1)

for i in range(1, m + 1):
    if q[i] == 0:	#主件
        options = []	#购买选择列表，其中每一项是由（购买的价格，满意度）组成
        cost = v[i]
        value = v[i] * w[i]
        options.append((cost, value))	#只买主件的花费和价格加入购买选择列表

        attachments = goods[i]	#这里是主件的附件列表

        if len(attachments) >= 1:
            a = attachments[0]
            options.append((v[i] + v[a], v[i] * w[i] + v[a] * w[a]))	#如果有一个以上附件，先加入一种选择，如果购买主键和附件1，将这种选择加入选择列表
			
        if len(attachments) >= 2:
            b = attachments[1]
            options.append((v[i] + v[b], v[i] * w[i] + v[b] * w[b]))#如果有两个附件，这是主键和附件的选择
            a = attachments[0]
            options.append(
                (v[i] + v[a] + v[b], v[i] * w[i] + v[a] * w[a] + v[b] * w[b])
            )	#这是主键和同时购买附件1，2的选择的价格和满意度

        for j in range(n, 0, -1):
            for c, val in options:
                if j >= c:
                    dp[j] = max(dp[j], dp[j - c] + val)		#z这一段是背包问题的最优解计算方法，不懂可以搜索 背包问题

print(dp[n])

思路见代码注释！

本题比较难，加油！