题解 | #购物单#

# 在不超过 N 元（可以等于 N 元）的前提下，使物品的价格与重要度的乘积的总和最大
# 0-1背包问题变种，买归类为附件的物品，必须先买该附件所属的主件
# 也就是说，主件的个数才是总的物品的个数
# 考虑每个物品时要考虑每种可能出现的情况：
#     1、主件，2、主件+附件1，3、主件+附件2，4、主件+附件1+附件2
# 求解各种情况下的子问题,自底向上求解即可

line = str(input())
N = int(line.split(' ')[0])  # 总金额
m = int(line.split(' ')[1])  # 希望购买的个数
id2info = {}
other2info = {}
for i in range(m):
    line = str(input())
    id = i+1
    v = int(line.split(' ')[0])  # 价格（10的倍数）
    p = int(line.split(' ')[1])  # 重要度
    q = int(line.split(' ')[2])  # 主0附id件
    if q == 0:
        # 主键
        id2info[id] = [v,p]
    else:
        # q是主键id
        if q in other2info:
            # 第二个附件
            other2info[q].append([v,p])
        else:
            # 第一个附件
            other2info[q] = [[v,p]]

# 子问题：求dp（i，j），即最大价格为j*10，可选主件为x1,...xi（前i个）时的最大价值
i_num = len(id2info)
j_num = N // 10
w, v= [[]], [[]]  # 这里预留了一个空list
# print(other2info)
# 记录四种情况下的价格与价值
for key in id2info:
    w_temp, v_temp = [], []
    #1、主件
    w_temp.append(id2info[key][0])
    v_temp.append(id2info[key][0]*id2info[key][1])
    #存在附件
    if key in other2info:
        #2、主件+附件1
        w_temp.append(w_temp[0]+other2info[key][0][0])
        v_temp.append(v_temp[0]+other2info[key][0][0]*other2info[key][0][1])
        #存在两主件
        if len(other2info[key])>1:
            #3、主件+附件2
            w_temp.append(w_temp[0]+other2info[key][1][0])
            v_temp.append(v_temp[0]+other2info[key][1][0]*other2info[key][1][1])
            w_temp.append(w_temp[0]+other2info[key][0][0]+other2info[key][1][0])
            #4、主件+附件1+附件2
            v_temp.append(v_temp[0]+other2info[key][0][0]*other2info[key][0][1]+other2info[key][1][0]*other2info[key][1][1])
    w.append(w_temp)
    v.append(v_temp)
# dp = [[0]*(j_num+1)]*(i_num+1)  # 会引发浅拷贝的问题，i_num+1个列表的内存会指向同一块
# 因此无论修改哪个[0]*(j_num+1)]，其余的i_num个也会跟着改变
dp = [[0]*(j_num+1) for _ in range(i_num+1)]
# dp[i][j] = max(物品不放入背包，主件，主件+附件1，主件+附件2，主件+附件1+附件2)
for i in range(1, i_num+1):
    for j in range(1, j_num+1):
        pre_max = dp[i-1][j]
        for x in range(len(w[i])):
            if j*10 - w[i][x] >= 0:
                pre_max = max(pre_max, dp[i-1][(j*10 - w[i][x])//10]+v[i][x])
        dp[i][j] = pre_max
print(dp[i_num][j_num])