题解 | #购物单#

from ctypes import Array
import sys

while True:
    try:
        #总价格，商品数量
        total, k = list(map(int, input().split()))
        #主商品
        main_key = []
        #权重满意度
        perPrice = {}
        #商品价格
        perValue = {}
        #主商品数据
        mainPrice = []
        mainValue = []
        for i in range(1, k + 1):
            perPrice[i] = [0, 0, 0]
            perValue[i] = [0, 0, 0]
        for i in range(1, k + 1):
            v, p, q = list(map(int, input().split()))
            vp = int(v*p/10)
            if q == 0:
                perPrice[i][0] = vp
                perValue[i][0] = int(v / 10)
                main_key.append(i)
            else:
                if perPrice[q][1] == 0:
                    perPrice[q][1] = vp
                    perValue[q][1] = int(v / 10)
                else:
                    perPrice[q][2] = vp
                    perValue[q][2] = int(v / 10)

        # for key in main_key:
        for key in perPrice.keys():
            if key in main_key:
                mainPrice.append(perPrice[key])
                mainValue.append(perValue[key])
        mm = len(mainPrice)
        nn = int(total / 10)
        dp = [[0] * (nn + 1) for _ in range(mm + 1)]
        for i in range(1, mm + 1):
            p1, p2, p3 = (
                    mainPrice[i - 1][0],
                    mainPrice[i - 1][1],
                    mainPrice[i - 1][2],
                )
            v1, v2, v3 = (
                mainValue[i - 1][0],
                mainValue[i - 1][1],
                mainValue[i - 1][2],
            )
            for j in range(nn + 1):
                dp[i][j] = dp[i - 1][j]
                if j - v1 >= 0:
                    dp[i][j] = max(dp[i][j], p1 + dp[i - 1][j - v1])
                if j - v1 - v2 >= 0:
                    dp[i][j] = max(dp[i][j], p1 + p2 + dp[i - 1][j - v1 - v2])
                if j - v1 - v3 >= 0:
                    dp[i][j] = max(dp[i][j], p1 + p3 + dp[i - 1][j - v1 - v3])
                if j - v1 - v2 - v3 >= 0:
                    dp[i][j] = max(
                        dp[i][j], p1 + p2 + p3 + dp[i - 1][j - v1 - v2 - v3]
                    )
        xx = dp[mm][nn]
        print(dp[mm][nn]*10)
    except:
        break