题解 | #购物单#

import sys
from collections import defaultdict

def run(n, ks):
    result = 0
    m = len(ks)
    d0 = [0]*(n//10+1)
    d1 = [0]*(n//10+1)
    vs = []
    for k,v in ks.items():
        _vs = [[v["a"][0]//10, v["a"][2]]]
        for i,v2 in enumerate(v["b"]):
            _vs.append([(v["a"][0]+v2[0])//10, v["a"][2]+v2[2]])
            if len(v["b"])-1 > i:
                for v3 in v["b"][i+1:]:
                    _vs.append([(v["a"][0]+v2[0]+v3[0])//10, v["a"][2]+v2[2]+v3[2]])
        vs.append(_vs)
    for i in range(1, m+1):
        d0=d1
        d1=[0]*(n//10+1)
        for j in range(1, n//10+1):
            d1[j] = d0[j]
            tmp  = [k for k in vs[i-1] if j-k[0]>=0]
            if len(tmp) > 0:
                tmp = max([d0[j-k[0]]+k[1] for k in tmp])
                d1[j] = max(d0[j], tmp)
    result = d1[n//10]
    return result

N, m = input().strip().split()
N, m = int(N), int(m)

ks = defaultdict(lambda: {"a":[],"b":[]})
for i in range(1,m+1):
    k = input().strip()
    k = list(map(int, k.split()))
    if k[2] > 0:
        ks[k[2]]["b"].append([k[0],k[1],k[0]*k[1]])
    else:
        ks[i]["a"] = [k[0],k[1], k[0]*k[1]]
result = run(N,ks)
print(result)