题解 | #购物单#

N, m = map (int, input().split())
main, aux = {}, {}
N = int(N/ 10)
for i in range(1, m + 1):
    v, p, q = map(int, input().split())
    v = int(v/10)
    if q == 0:
        main[(i, 0)] = (v, p*v)
    else:
        if (q, 0) not in aux:
            aux[(q, 0)] = (v, p*v)
        else:
            aux[(q, 1)] = (v, p*v)
for i in range(1, m + 1):
    if (i, 0) in aux:
        if (i, 0) in aux:
            if (i, 1) in aux:
                main[(i, 1)] = (main[(i, 0)][0] + aux[(i, 0)][0], main[(i, 0)][1] + aux[(i, 0)][1])
                main[(i, 2)] = (main[(i, 0)][0] + aux[(i, 1)][0], main[(i, 0)][1] + aux[(i, 1)][1])
                main[(i, 3)] = (main[(i, 0)][0] + aux[(i, 0)][0] + aux[(i, 1)][0], main[(i, 0)][1] + aux[(i, 0)][1] + aux[(i, 1)][1])
            else:
                main[(i, 1)] = (main[(i, 0)][0] + aux[(i, 0)][0], main[(i, 0)][1] + aux[(i, 0)][1])
dp = [[0] * (N + 1) for _ in range(m+2)]
for i in range(1, m + 1):
    dp[i][0] = 0
    for j in range(1, N + 1):
        if (i,3) in main:
            temp = 0
            dpmax = 0
            for k in range(4):
                if j >= main[(i, k)][0]:
                    temp = max(dp[i-1][j], dp[i-1][j-main[(i, k)][0]] + main[(i, k)][1])
                else:
                    temp = dp[i-1][j]
                dpmax = max(dpmax, temp)
            dp[i][j] = dpmax
        elif (i,1) in main:
            temp = 0
            dpmax = 0
            for k in range(2):
                if j >= main[(i, k)][0]:
                    temp = max(dp[i-1][j], dp[i-1][j-main[(i, k)][0]] + main[(i, k)][1])
                else:
                    temp = dp[i-1][j]
                dpmax = max(dpmax, temp)
            dp[i][j] = dpmax
        elif (i,0) in main:
            if j >= main[(i, 0)][0]:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-main[(i, 0)][0]] + main[(i, 0)][1])
            else:
                dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = dp[i-1][j]
        # print(i,j, dp[i][j])
print(dp[m][N] * 10)