题解 | #购物单#

money, nums = list(map(int, input().split()))

w = {}  # 存储重量，即花的钱
v = {} # 存储价值，即满意度

zhu = {}  # 存储主件信息
fu ={} # 存储附件信息

for i in range(1, nums + 1):  # 读取输出
    a, b, c = list(map(int, input().split())) # 价格 权重 是否主件
    if c == 0:
        zhu[i] = [a, b] # 主件是二维的
    else:
        if c not in fu:  # 该主件未存储相关的附件
            fu[c] = [[a, b]]
        else:
            fu[c].append([a, b]) # 附件是三维的 ,拼接附件

# print(zhu,fu)

for k in zhu:  # 以遍历主件作为外层循环
    w[k] = [zhu[k][0]]  # 只买主件的情况，花的钱
    v[k] = [zhu[k][0]*zhu[k][1]] # 满意度
    
    # 买一件的情况
    if k in fu:   # 如果主件存在附件
        w[k].append(zhu[k][0] + fu[k][0][0]) # 花多少钱是二维的，主件加第一个附件的钱
        v[k].append(v[k][0] + fu[k][0][0]*fu[k][0][1]) # 满意度是二维的，件加第一个附件的满意度

        if len(fu[k]) > 1: # 如果主件存在两个附件
            w[k].append(zhu[k][0] + fu[k][0][0] + fu[k][1][0]) # 三件花的钱
            v[k].append(v[k][1] + fu[k][1][0]*fu[k][1][1]) #三件的满意度
            #只买第二个附件
            w[k].append(zhu[k][0] + fu[k][1][0])
            v[k].append(v[k][0] + fu[k][1][0]*fu[k][1][1])
    # print(fu,zhu)
    # print(w,v)

dp = [0]*(money+1)


for i in zhu:
    for m in range(money, -1, -10):  #从后往前遍历钱，前面的数据就相当于上一次遍历的数据
        max_manyi = dp[m]
        for j in range(len(w[i])):
            if m - w[i][j] >= 0:
                max_manyi = max(max_manyi, dp[m - w[i][j]] + v[i][j])
        dp[m] = max_manyi
    # print(dp)

print(dp[money])