题解 | #购物单#

import sys
#a = [[4, 2, 0, 0, 0, 0], [3, 2, 1, 1, 0, 0], [5, 2, 1, 2, 0, 0], [6, 2, 0, 3, 0, 0], [7, 2, 4, 4, 0, 0]]
#a=[[价格,重要度,主件编号,序号,主件附件标记,附件数量]]
p, m = map(int, input().split())
p = p // 10
a = sys.stdin.readlines()
for i, x in zip(range(m), a):
    a[i].rstrip()
    a[i] = list(map(int, x.split())) + [i, 0, 0]
    a[i][0] //= 10

for i, x in zip(range(m), a):
    if x[2] != 0:
        x[3] = a[x[2]-1][3]
        x[4] = 0
        a[x[2]-1][5] += 1
    else:
        x[4] = 1

a.sort(key=lambda x:(x[3], x[4]))
dp = [[0 for _ in range(p+1)] for _ in range(m+1)]

#1 <= i <= m
#1 <= j <= p

for i in range(1, m+1):
    for j in range(1, p+1):
        v_current = a[i-1][0]
        p_current = a[i-1][1]
        l_current = a[i-1][5]
        flag = a[i-1][4]
        if flag == 0:
            if j >= v_current:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-v_current] + p_current*v_current)
            else:
                dp[i][j] = dp[i-1][j]
        else:
            if j >= v_current:
                dp[i][j] = max(dp[i-l_current-1][j], dp[i-1][j-v_current] + p_current*v_current)
            else:
                dp[i][j] = dp[i-l_current-1][j]
print(dp[m][p]*10)