描述

王强决定把年终奖用于购物，他把想买的物品分为两类：主件与附件。
主件可以没有附件，至多有 2个附件。附件不再有从属于自己的附件。如果要买归类为附件的物品，必须先买该附件所属的主件，且每件物品只能购买一次。

王强查到了每件物品的价格，而他只有 n元的预算。为了先购买重要的物品，他给每件物品规定了一个重要度，用整数 1∼5表示。他希望在花费不超过 n 元的前提下，使自己的满意度达到最大。
满意度是指所购买的每件物品的价格与重要度的乘积的之和，具体地说，记第 ii 件物品的价格为 vi​，重要度为 wi​；现在，一共选中了 k 件物品，编号依次为 j1,j2,…,jkj​，则满意度计算为：

∑i=1kvji×wji=vj1wj1+vj2wj2+⋯+vjkwjki=1

请你帮助王强计算可获得的最大的满意度。

输入描述：

第一行输入两个整数 n,m(1≦n≦32000,1≦m≦60)n 代表预算、需要购买的物品总数。
此后 m 行，第 i 行输入三个整数 vi​,wi​,qi​(1≦vi​≦104; 1≦wi​≦5; 0≦qi​≦m) 代表第 i 件物品的价格、重要度、主件编号。特别地，qi=0代表该物品为主件。编号即输入顺序，从 1 开始。

特别地，保证全部物品的价格 vv 均为 10 的倍数。

输出描述：

在一行上输出一个整数，代表王强可获得的最大满意度。

解答：

#n:预算，m：需要购买的物品总数

n,m = map(int,input().split())

#构建主件和附件的字典以存储相关信息

main_info = {}

accessory_info = {}

#读取物品，判断其是主件还是附件

for i in range(m):

    #vi:第i件物品的价格，wi：第i件物品的重要度，qi:主件编号（0为主件）

    #！一定需要注意，这里的数据输入一定要和数据处理写进一个循环

    vi,wi,qi = map(int,input().split())

    #如果是主件

    if qi==0:

        main_info[i+1]=[vi,wi]

    #如果是附件

    else:

        #由于附件从属于主件，故要在主件的基础上考虑

        if qi in accessory_info:

            accessory_info[qi].append([vi,wi])

        else:

            accessory_info[qi]=[[vi,wi]]

#构建物品组合，即主件/主件+附件1/主件+附件2/主件+附件1+附件2

values=[[]]#存储第i组物品的可选价格

weights=[[]]#存储对应的总重要度

#遍历每一个主件

for key in main_info:

    value = []#临时存储当下情况的价格

    weight = []#临时存储当下情况的重要度

    v0,w0 = main_info[key]#从主件字典里面释放出主件的价格和重要度

    #（1）只购买主件

    value.append(v0)

    weight.append(w0*v0)

    #(2)同时也购买附件

    if key in accessory_info:

        #[1]主件+附件1

        v1,w1 = accessory_info[key][0]#释放第一个附件的价格和重要度

        value.append(v0+v1)

        weight.append(w0*v0+w1*v1)

        #[2]主件+附件2

        if len(accessory_info[key])>1:

            v2,w2 = accessory_info[key][1]

            value.append(v0+v2)

            weight.append(w0*v0+w2*v2)

            #[3]主件+附件1+附件2

            value.append(v0+v2+v1)

            weight.append(w0*v0+w2*v2+w1*v1)

    #将所有情况都存储在物品组合的大集合里

    values.append(value)

    weights.append(weight)

#构建dp[i][j]数组表示使用预算j×10购买前i种物品的满意度，其中i代表选取前i种物品加入，j代表预算为j×10

money = n//10#将预算转换为10的倍数

main_num = len(main_info)#计算主件的数量

dp = [[0]*(money+1) for _ in range(main_num+1)]

#动态规划求解

for i in range(1,main_num+1):#遍历所有主件

    for j in range(1,money+1):#遍历所有预算

        #不购买当前的主件

        dp[i][j]=dp[i-1][j]

        #购买当前的主件，遍历所有可能

        for k in range(len(values[i])):

            if j*10>=values[i][k]:#预算必须足够

                dp[i][j] = max(dp[i][j],dp[i-1][(j*10-values[i][k])//10]+weights[i][k])

print(dp[i][j])