题解 | #购物单#

#coding=utf-8
if __name__=="__main__":
    budget,n_goods=[int(i) for i in input().split()]
    budget=budget//10
    prime=[] #主件
    prime_pos=[]
    prime_affi={} #主附件
    for i in range(n_goods):
        goods=[int(t) for t in input().split()]
        goods[0]//=10
        goods[1]=goods[0]*goods[1]
        if goods[2]==0:
            prime.append(goods)
            prime_pos.append(i+1)
        else:
            if goods[2] in prime_affi:
                prime_affi[goods[2]].append(goods)
            else:
                prime_affi[goods[2]]=[goods]
                
    dp=[[0]*(budget+1) for _ in range(len(prime)+1)]
    for i in range(1,len(prime)+1):
        for cmoney in range(1,budget+1):
            goods=prime[i-1]
            if goods[0]>cmoney:
                #买不起
                dp[i][cmoney]=dp[i-1][cmoney]
            else:
                maxp1=max(dp[i-1][cmoney],dp[i-1][cmoney-goods[0]]+goods[1]) #不加入i or 加入i
                if prime_pos[i-1] in prime_affi:
                    #该主件存在附件
                    affs=prime_affi[prime_pos[i-1]]
                    for af in affs:
                        if af[0]+goods[0]<=cmoney:
                            maxp1=max(maxp1,dp[i-1][cmoney-goods[0]-af[0]]+goods[1]+af[1])
                    
                    if len(affs)==2:
                        tmp=affs[0][0]+affs[1][0]+goods[0]
                        if tmp<=cmoney:
                            maxp1=max(maxp1,dp[i-1][cmoney-tmp]+affs[0][1]+affs[1][1]+goods[1])
                dp[i][cmoney]=maxp1
    print(dp[-1][-1]*10)