题解 | #购物单#

n,m=map(int,input().split())
primary={}
for i in range(1,m+1):
    v,p,q=map(int,input().split())
    if q==0 and i not in primary:
        primary[i]=[[v,p]]
    elif q!=0 and q not in primary:
        primary[q]=[[0,0]]
        primary[q].append([v,p] )
    elif  q!=0 and q in primary:
            primary[q].append([v,p] ) 
    else:
         primary[i][0]=[v,p]



m=len(primary)
v=[[]]
w=[[]]
for key in primary:
    v_temp=[primary[key][0][0]]
    w_temp=[primary[key][0][0]*primary[key][0][1]]
    if len(primary[key])>1:
        v_temp.append(primary[key][1][0]+primary[key][0][0])
        w_temp.append(primary[key][1][0]*primary[key][1][1]+primary[key][0][0]*primary[key][0][1])
    #注意一个主件，两个附件时，有单主件，主件+附件1，主件+附件2，主键+附件1和2
    if len(primary[key])==3:
        v_temp.append(primary[key][0][0]+primary[key][2][0])
        v_temp.append(primary[key][1][0]+primary[key][0][0]+primary[key][2][0])
        w_temp.append(primary[key][0][0]*primary[key][0][1]+primary[key][2][0]*primary[key][2][1])
        w_temp.append(primary[key][1][0]*primary[key][1][1]+primary[key][0][0]*primary[key][0][1]+primary[key][2][0]*primary[key][2][1])
    v.append(v_temp)
    w.append(w_temp)

#简言之，即先对一个主件几种组合求max，再进入动态规划
dp=[[0]*(n+1) for _ in range(m+1)]
for i in range(1,m+1):
    for j in range(10,n+10,10):
        max_i=dp[i-1][j]
        for k in range(len(v[i])):
             if j-v[i][k]>=0:
                max_i=max(max_i,dp[i-1][j-v[i][k]]+w[i][k])
        dp[i][j]=max_i

print(dp[m][n])