题解 | #购物单#

class HJ16:
    def __init__(self):
        self.index = 0
        self.v = [0]
        self.p = 0
        self.q = 0
        self.w = [0]
        self.next = []


T = input().split()
N, m = int(T[0]), int(T[1])
ls_HJ16 = []
for i in range(m + 1):
    ls_HJ16_temp = HJ16()
    ls_HJ16.append(ls_HJ16_temp)
ls_main = []
for i in range(1, m + 1):
    temp = input().split()
    ls_HJ16[i].index = i
    ls_HJ16[i].v[0] = int(temp[0])
    ls_HJ16[i].p = int(temp[1])
    ls_HJ16[i].q = int(temp[2])
    ls_HJ16[i].w[0] = ls_HJ16[i].v[0] * ls_HJ16[i].p
    if ls_HJ16[i].q != 0:
        ls_HJ16[ls_HJ16[i].q].next.append(i)
    else:
        ls_main.append(i)

ii = 1
for i in ls_main:
    ls_HJ16[i].index = ii
    ii += 1
    next0v, next0w, next1v, next1w = 0, 0, 0, 0
    if len(ls_HJ16[i].next) != 0:
        next0v = ls_HJ16[ls_HJ16[i].next[0]].v[0]
        next0w = ls_HJ16[ls_HJ16[i].next[0]].w[0]
        ls_HJ16[i].v.append(ls_HJ16[i].v[0] + next0v)
        ls_HJ16[i].w.append(ls_HJ16[i].w[0] + next0w)
    if len(ls_HJ16[i].next) == 2:
        next1v = ls_HJ16[ls_HJ16[i].next[1]].v[0]
        next1w = ls_HJ16[ls_HJ16[i].next[1]].w[0]
        ls_HJ16[i].v.append(ls_HJ16[i].v[0] + next1v)
        ls_HJ16[i].w.append(ls_HJ16[i].w[0] + next1w)
        ls_HJ16[i].v.append(ls_HJ16[i].v[0] + next0v + next1v)
        ls_HJ16[i].w.append(ls_HJ16[i].w[0] + next0w + next1w)

dp = [[0] * (N // 10 + 1) for _ in range(len(ls_main) + 1)]
# dp=[[0]*(N+1)]*(len(ls_main)+1)
for i in [0] + ls_main:
    for j in range(N // 10 + 1):
        max_dp = dp[ls_HJ16[i].index - 1][j]
        for k in range(len(ls_HJ16[i].v)):
            if j >= ls_HJ16[i].v[k] // 10:
                max_dp = max(
                    max_dp,
                    dp[ls_HJ16[i].index - 1][j - ls_HJ16[i].v[k] // 10]
                    + ls_HJ16[i].w[k],
                )
        dp[ls_HJ16[i].index][j] = max_dp
print(dp[len(ls_main)][N // 10])