题解 | #购物单#

total_money, sum = map(int, input().split())
goods_dic = {}
for i in range(1, sum+1):
    v, p, q = map(int, input().split())
    v //= 10
    if q == 0:
        if i not in goods_dic:
            goods_dic[i] = [[v, v*p]]
        else:
            for lst in goods_dic[i]:
                lst[0] += v
                lst[1] += v*p
            goods_dic[i].append([v, v*p])
    else:
        if q not in goods_dic:
            goods_dic[q] = [[v, v*p]]
        else:
            le = len(goods_dic[q])
            for i in range(le):
                x, y = goods_dic[q][i]
                goods_dic[q].append([x+v, y+v*p])


goods_lst = []
for key, value in goods_dic.items():
    goods_lst.append(value)

le = len(goods_lst)
dp = [[0 for _ in range(total_money//10+1)] for _ in range(le+1)]

for i in range(1, le+1):
    for j in range(1, total_money//10+1):
        for lst in goods_lst[i-1]:
            v, w = lst
            if v == j:
                dp[i][j] = max(dp[i-1][j], w, dp[i][j])
            if v < j:
                dp[i][j] = max(dp[i-1][j], w + dp[i-1][j-v], dp[i][j])
            if v > j:
                dp[i][j] = max(dp[i-1][j], dp[i][j])

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