题解 | #购物单#

from collections import defaultdict
line = input().split(" ")
# 除以10是必须的，不然会超时
N = int(line[0]) // 10
m = int(line[1])

prices = defaultdict(lambda: [0, 0, 0])
values = defaultdict(lambda: [0, 0, 0])

for i in range(1, m+1):
    v, p, q = map(int, input().split(" "))
    v //= 10
    # 代表这个是主件
    if q == 0:
        prices[i][0] = v
        values[i][0] = v * p
    elif prices[q][1]:
        prices[q][2] = v
        values[q][2] = v * p
    else:
        prices[q][1] = v
        values[q][1] = v * p

# 开辟一个一维的dp数组
dp = [0] * (N + 1)

for q in prices:
    p1, p2, p3 = prices[q]
    v1, v2, v3 = values[q]
    # 一维数组需要倒序遍历
    for j in reversed(range(N + 1)):
        if j >= p1:
            dp[j] = max(dp[j], dp[j - p1] + v1)
        if j >= p1 + p2:
            dp[j] = max(dp[j], dp[j - p1 - p2] + v1 + v2)
        if j >= p1 + p3:
            dp[j] = max(dp[j], dp[j - p1 - p3] + v1 + v3)
        if j >= p1 + p2 + p3:
            dp[j] = max(dp[j], dp[j - p1 - p2 - p3] + v1 + v2 + v3)

print(dp[N] * 10