题解 | #购物单#

N, m = input().split()
N, m = int(N), int(m)
goods = []

class Goods:
    def __init__(self):
        self.price = int
        self.value = int
        self.q = int
goods = []
for _ in range(0, m):
    goods.append(Goods())
#负载价值表
w = [[0]*4 for i in range(0,m)]
v = [[0]*4 for i in range(0,m)]

for i in range(0, m):
    a,b,c = input().split(" ")
    temp = goods[i]
    temp.price ,temp.value,temp.q = int(a), int(b), int(c)
    if int(c) == 0:
        w[i][0] = w[i][1] = w[i][2] = w[i][3] = temp.price
        v[i][0] = v[i][1] = v[i][2] = v[i][3] = temp.price * temp.value

#计算好附件的价值
for i in range(0, m):
    if goods[i].q !=0:
        #主件索引等于主件编号-1
        t = goods[i].q -1
        #判断已有附件个数
        #无附件
        if w[t][0] == w[t][1]:
            w[t][1] += goods[i].price
            v[t][1] += goods[i].price * goods[i].value
        #一个附件
        else:
            w[t][2] += goods[i].price
            v[t][2] += goods[i].price * goods[i].value

        w[t][3] += goods[i].price
        v[t][3] += goods[i].price * goods[i].value



# w = [[0*4]*m]
# v = [[0*4]*m]
#dp[i][j]  第i个主件 j预算
dp = [[0]*(N//10+1) for  i in range(0,m+1)]
#主件

for i in range(0,N+1,10):
    count = 0
    for j in  range(0, m):
        p = goods[j].q
        #是主件
        if p == 0:
            count +=1
            # 负载价值表索引为j
            # dp 表预算索引为 i//10
            

            dp[count][i//10]= dp[count-1][i//10]
            for k in  range(0,4):
                if i >= w[j][k]:
                    dp[count][i//10] = max(dp[count][i//10],dp[count-1][i//10-w[j][k]//10]+v[j][k])


print(dp[count][N//10])