题解 | #购物单#

money, number = list(map(int, input().strip().split()))
money = money // 10
main = [[[0, 0], [0, 0], [0, 0]] for _ in range(number + 2)]
for i in range(1, 1 + number):
    v, p, q = list(map(int, input().strip().split()))
    if q == 0:  # 主件
        main[i][0] = [v // 10, v * p]
    else:
        if main[q][1][0] == 0:
            main[q][1] = [v // 10, v * p]
        else:
            main[q][2] = [v // 10, v * p]
main = [i for i in main if i[0][0] != 0]
dp = [[0 for i in range(1 + money)] for j in range(1 + len(main))]
for num in range(1, 1 + len(main)):
    for mon in range(1 + money):
        dp[num][mon] = dp[num - 1][mon]
        (p1, v1), (p2, v2), (p3, v3) = main[num - 1]
        # 不买前一个物品买这个物品和不买这个物品的最大值
        if mon >= p1:
            dp[num][mon] = max(dp[num][mon], dp[num - 1][mon - p1] + v1)
        if mon >= p1 + p2:
            dp[num][mon] = max(dp[num][mon], dp[num - 1][mon - p1 - p2] + v1 + v2)
        if mon >= p1 + p3:
            dp[num][mon] = max(dp[num][mon], dp[num - 1][mon - p1 - p3] + v1 + v3)
        if mon >= p1 + p2 + p3:
            dp[num][mon] = max(dp[num][mon], dp[num - 1][mon - p1 - p2 - p3] + v1 + v2 + v3)
print(dp[-1][-1])