题解 | #购物单#

N, m = map(int, input().split())
zhu = {}
fu = {}

for k in range(1, m + 1):
    v, p, q = map(int, input().split())
    if q == 0:
        zhu[k] = [v, v * p]
    else:
        if q in fu:
            fu[q].append([v, v * p])
        else:
            fu[q] = [[v, v * p]]

#print(">>>zhu=", zhu)
#print(">>>fu=", fu)

dp = [0 for j in range(N + 1)]

for k, t in zhu.items():
    w = []
    va = []

    w.append(t[0])
    va.append(t[1])

    if k in fu:
        # 主件 + 附件1
        w.append(w[0] + fu[k][0][0])
        va.append(va[0] + fu[k][0][1])

        if len(fu[k]) > 1:  # 表示有两个以上附件
            # 主件 + 附件2
            w.append(w[0] + fu[k][1][0])
            va.append(va[0] + fu[k][1][1])
            # 主件 + 附件1 + 附件2
            w.append(w[0] + fu[k][0][0] + fu[k][1][0])
            va.append(va[0] + fu[k][0][1] + fu[k][1][1])

    # print('>>>w=', w)
    # print('>>>va=', va)

    # 处理数据,注意此处for的缩进
    for j in range(N, -1, -10):
        for i, _ in enumerate(w):  # w代表价格

            if j >= w[i]:
                dp[j] = max(dp[j], dp[j - w[i]] + va[i])

# 输出
print(dp[N])