题解 | #购物单#

N,n=list(map(int,input().split()))
N=int(N/10)
V=[[0]*6 for _ in range(n)]
for i in range(n):
    v,p,q=list(map(int,input().split())) 
    v=int(v/10)
    if q==0:
        V[i][0],V[i][1]= v,v*p
    else:
        j=1
        if V[q-1][2]!=0:
            j=2
        V[q-1][2*j],V[q-1][2*j+1],V[i][0],V[i][1]=v,v*p,0,0
dp=[[0]*int(N+1) for _ in range(n+1)]
for i in range(1,n+1):  
    for j in range(N+1):
        dp[i][j]=dp[i-1][j]
        if j-V[i-1][0]>=0:
            dp[i][j]=max(dp[i][j],dp[i-1][j-V[i-1][0]]+V[i-1][1])
        if j-V[i-1][0]-V[i-1][2]>=0:
            dp[i][j]=max(dp[i][j],dp[i-1][j-V[i-1][0]-V[i-1][2]]+V[i-1][1]+V[i-1][3])
        if j-V[i-1][0]-V[i-1][4]>=0:  
            dp[i][j]=max(dp[i][j],dp[i-1][j-V[i-1][0]-V[i-1][4]]+V[i-1][1]+V[i-1][5])
        if j-V[i-1][0]-V[i-1][2]-V[i-1][4]>=0:
            dp[i][j]=max(dp[i][j],dp[i-1][j-V[i-1][0]-V[i-1][2]-V[i-1][4]]+V[i-1][1]+V[i-1][3]+V[i-1][5])
print(dp[n][N]*10)