题解 | #购物单#

money,length = map(int,input().split())
money //= 10
goods = dict()
for i in range(1,length+1):
    v,p,q = map(int, input().split())
    v //= 10
    if q == 0:
        if i not in goods.keys():
            goods[i] = [[v, v*p], [0, 0], [0, 0]]
        else:
            goods[i][0] = [v, v*p]
    else:
        if q not in goods.keys():
            goods[q] = [[0, 0], [v, v*p], [0, 0]]
        elif goods[q][1] == [0, 0]:
            goods[q][1] = [v, v*p]
        else:
            goods[q][2] = [v, v*p]
dp = [0]*(money+1)
for k,v in goods.items():
    for j in range(money ,v[0][0]-1 ,-1):
        dp[j] = max(dp[j],dp[j-v[0][0]] + v[0][1])
        if j >= v[0][0]+v[1][0]:
            dp[j] = max(dp[j],dp[j-v[0][0]-v[1][0]] + v[0][1]+v[1][1])
        if j >= v[0][0]+v[2][0]:
            dp[j] = max(dp[j],dp[j-v[0][0]-v[2][0]] + v[0][1]+v[2][1])
        if j >= v[0][0]+v[1][0]+v[2][0]:
            dp[j] = max(dp[j],dp[j-v[0][0]-v[1][0]-v[2][0]] + v[0][1]+v[1][1]+v[2][1])
print(dp[money] * 10)