题解 | #购物单#

while True:
    try:
        l1 = list(map(int, input().split()))
        money = int(l1[0] / 10)
        tt = [[0, 0, 0] for i in range(l1[1])]  # 价格
        vi = [[0, 0, 0] for i in range(l1[1])]  # 满意度
        for i in range(l1[1]):
            res = list(map(int, input().split()))
            if res[2] != 0:
                if tt[res[2] - 1][1] == 0:
                    tt[res[2] - 1][1] = int(res[0] / 10)
                    vi[res[2] - 1][1] = res[1] * int(res[0] / 10)
                else:
                    tt[res[2] - 1][2] = int(res[0] / 10)
                    vi[res[2] - 1][2] = res[1] * int(res[0] / 10)
            else:
                tt[i][0] = int(res[0] / 10)
                vi[i][0] = res[1] * int(res[0] / 10)

        for i in range(l1[1]):
            if [0, 0, 0] in tt:
                tt.remove([0, 0, 0])

        for i in range(l1[1]):
            if [0, 0, 0] in vi:
                vi.remove([0, 0, 0])

        # print(tt, vi)
        dp = [[0] * (money + 1) for i in range(len(tt) + 1)]

        for i in range(1, len(tt) + 1):
            for j in range(money + 1):
                j0, j1, j2 = tt[i - 1]
                w0, w1, w2 = vi[i - 1]

                # 关键一步，先把上一次的最优解搬过来 最优低保
                dp[i][j] = dp[i-1][j]

                # 判断上一步最优解和 剩余空间最优解+上一步最优解 谁更优 如果比不过至少有个低保
                # 如果直接 dp[i][j] = max(dp[i - 1][j - j0] + w0, dp[i-1][j]) 比不过就没低保为0

                # 灵活变通
                # 如果 dp[i][j] = max(dp[i][j - j0] + w0, dp[i][j]) 则是有放回的拿 价值会更高
                
                if j >= j0:
                    dp[i][j] = max(dp[i - 1][j - j0] + w0, dp[i][j])

                if j >= j0 + j1:
                    dp[i][j] = max(dp[i - 1][j - j0 - j1] + w0 + w1, dp[i][j])

                if j >= j0 + j2:
                    dp[i][j] = max(dp[i - 1][j - j0 - j2] + w0 + w2, dp[i][j])

                if j >= j0 + j1 + j2:
                    dp[i][j] = max(dp[i - 1][j - j0 - j1 - j2] + w0 + w1 + w2,
                                   dp[i][j])

        # print(dp)
        print(dp[-1][-1] * 10)

    except EOFError:
        break
# 1000 5
# 800 2 0
# 400 5 1
# 200 5 1
# 400 3 0
# 500 2 0