题解 | #购物单#

n, m = map(int, input().split())
n = n // 10
w_dict, v_dict, fwv_list = {}, {}, []
for i in range(1, m + 1):
    v, p, q = map(int, input().split())
    v = v // 10
    if q == 0:
        w_dict[i] = [v]
        v_dict[i] = [v * p]
    else:
        fwv_list.append([q, v, v * p])

for q, w, v in fwv_list:
    for index in range(len(w_dict[q])):
        w_dict[q].append(w_dict[q][index] + w)
    for index in range(len(v_dict[q])):
        v_dict[q].append(v_dict[q][index] + v)

w_list, v_list = [[0]]+list(w_dict.values()), [[0]]+list(v_dict.values())
mm = len(w_dict)
dp = [[0] * (n + 1) for _ in range(mm + 1)]
for i in range(1, mm + 1):
    for j in range(1, n + 1):
        tw = dp[i - 1][j]
        for k in range(len(w_list[i])):
            if j >= w_list[i][k]:
                tw = max(tw, dp[i - 1][j - w_list[i][k]] + v_list[i][k])
        dp[i][j] = tw
print(max(max([i for i in dp])) * 10)