题解 | #购物单#

weight = {}
value = {}
tmp = {} # 存储附件

N, m = list(map(int, input().split())) # 总钱数 商品个数

for i in range(1, m+1):
    v, p, q = list(map(int, input().split())) # 价格 重要度 是否主件
    if q == 0:
        value[i] = [v*p]
        weight[i] = [v/10]
    else:
        if q not in tmp:
            tmp[q] = [(v, p)]
        else:
            tmp[q].append((v, p))

for k, val in tmp.items():
    for (v, p) in val:
        weight[k].append(v/10)
        value[k].append(v*p)

v, w = list(value.values()), list(weight.values()) # 满意度 价格
for i in range(len(w)):
    if len(w[i]) == 1:
        continue
    v[i].append(v[i][0] + v[i][-1])
    w[i].append(w[i][0] + w[i][-1])
    for j in range(1, len(w[i])-1):
        w[i][j] += w[i][j-1]
        v[i][j] += v[i][j-1]



count = len(v)
dp = [[0]*(N//10+1) for _ in range(count + 1)]
for i in range(1, count + 1):
    for money in range(1, N // 10 + 1):
        max_v = dp[i-1][money]
        for j in range(len(w[i-1])):
            if money - w[i-1][j] >= 0:
                max_v = max(max_v, dp[i-1][int(money-w[i-1][j])] + v[i-1][j])
        dp[i][money] = max_v    

print(dp[-1][-1])