题解 | #购物单#

import sys


class Item:
    def __init__(self, v, p, q):
        self.v = int(v)//10
        self.p = int(p)
        self.q = int(q)
        self.s = self.v * self.p
        self.a = []  # Accessories

# 1 Process input.
N, m = next(sys.stdin).split()
N, m = int(N)//10, int(m)
g = [None]  # List of all goods.
for line in sys.stdin:
    item = Item(*line.split())
    g.append(item)
h = []
for i in range(1, len(g)):
    item = g[i]
    if item.q == 0:
        h.append(item)
    else:
        g[item.q].a.append(item)
g = None
# 2 DP.
dp = [[0] * (N+1), [0] * (N+1)]
for i in range(len(h)):
    a = h[i].a
    ps = [(h[i].v, h[i].s)]  # All possibilities.
    if len(a) > 0:
        ps.append((h[i].v+a[0].v, h[i].s+a[0].s))
    if len(a) > 1:
        ps.append((h[i].v+a[1].v, h[i].s+a[1].s))
        ps.append((h[i].v+sum(x.v for x in a), h[i].s+sum(x.s for x in a)))
    for p in ps:
        for j in range(N, p[0]-1, -1):
            dp[1][j] = max(dp[0][j-p[0]]+p[1], dp[1][j])
    dp[0] = list(dp[1])
                
print(dp[1][N]*10)