题解 | #购物单#

# 2024年10月29日  周二   下午15:08


N, m = list(map(int, input().split()))
zhu = {}
fu = {}
for i in range(1, m + 1):
    v, p, q = list(map(int, input().split()))
    if q == 0:
        zhu[i] = [v, v * p]
    else:
        if q not in fu:
            fu[q] = [[v, v * p]]
        else:
            fu[q].append([v, v * p])
#print(zhu)
#print(fu)
dp = [0] * (N + 1)
for k, t in zhu.items():
    w = []
    va = []
    w.append(t[0])
    va.append(t[1])
    if k in fu:
        # for a,b in fu.items():  # 千万记住这里不能对附件列表进行完全循环访问，如果fu={1: [[300, 1500], [400, 2000]], 5: [[500, 2000], [400, 1200]]},就会出错
        w.append(t[0] + fu[k][0][0])
        va.append(t[1] + fu[k][0][1])
        if len(fu[k]) > 1:
            w.append(t[0] + fu[k][1][0])
            va.append(t[1] + fu[k][1][1])

            w.append(t[0] + fu[k][0][0] + fu[k][1][0])
            va.append(t[1] + fu[k][0][1] + fu[k][1][1])
    #print(w)
    #print(va)
    for j in range(N, -1, -10):  # 一定要注意这里for循环的缩进，还有外循环是对N进行循环（符合动态规划要求，外循环要倒着来，内循环正常）
        for c, d in enumerate(w):
            if j >= d:
                dp[j] = max(dp[j], dp[j - d] + va[c])
print(dp[N])