题解 | #购物单#

bag_content, num = map(int, input().split())

ths = {}
add_ths = {}

for i in range(1, num+1):
    v, p, q = map(int, input().split())
    if q == 0: # 主件
        ths[i] = [v, p]
    else:
        if q in add_ths.keys():
            add_ths[q].append([v, p])
        else:
            add_ths[q] = [[v, p]]
# print(ths, add_ths)
ths_num = len(ths)

w, v = [[]], [[]]
for key in ths:
    w_temp, v_temp = [], []
    w_temp.append(ths[key][0])
    v_temp.append(ths[key][0]*ths[key][1])
    if key in add_ths.keys():
        w_temp.append(w_temp[0]+add_ths[key][0][0])
        v_temp.append(v_temp[0]+add_ths[key][0][0]*add_ths[key][0][1])
        if len(add_ths[key]) > 1:
            w_temp.append(w_temp[0]+add_ths[key][1][0])
            v_temp.append(v_temp[0]+add_ths[key][1][0]*add_ths[key][1][1])
            w_temp.append(w_temp[0]+add_ths[key][0][0]+add_ths[key][1][0])
            v_temp.append(v_temp[0]+add_ths[key][0][0]*add_ths[key][0][1]+add_ths[key][1][0]*add_ths[key][1][1])

    w.append(w_temp)
    v.append(v_temp)
# print(w,v)

dp = [[0]*(ths_num+1) for _ in range(0, bag_content//10 + 1)]
for weight in range(1, bag_content//10 + 1):
    for t_num in range(1, ths_num+1):
        max_i = dp[weight][t_num-1]
        for n in range(len(w[t_num])):
            if weight - w[t_num][n]//10 >= 0:
                max_i = max(max_i, dp[weight - w[t_num][n]//10][t_num-1] + v[t_num][n])
        dp[weight][t_num] = max_i
# print(dp)
print(dp[bag_content//10][ths_num])