题解 | #购物单#

import sys
input = sys.stdin.read
def max_satisfaction(N, m, items):
    dp = [0] * (N + 1)
    
    main_items = []
    attachments = [[] for _ in range(m + 1)]

    for index, (v, p, q) in enumerate(items):
        if q == 0:
            main_items.append((v, p, index + 1))
        else:
            attachments[q].append((v, p))

    for v, p, index in main_items:
        # 反向遍历保证dp数组的正确更新
        for j in range(N, v - 1, -1):
            # 只买主件
            dp[j] = max(dp[j], dp[j - v] + v * p)
            # 穷举所有附件组合
            for num in range(1, 1 << len(attachments[index])):  # 1 << len(attachments[index]) is 2^len(attachments[index])
                total_v = v
                total_p = v * p
                for k in range(len(attachments[index])):
                    if num & (1 << k):  # 检查第k个附件是否被选择
                        av, ap = attachments[index][k]
                        total_v += av
                        total_p += av * ap
                if j >= total_v:
                    dp[j] = max(dp[j], dp[j - total_v] + total_p)

    return max(dp)


def process_input(input_data):
    # 解析输入
    data = input_data.split()
    N = int(data[0])
    m = int(data[1])
    items = []
    index = 2
    for _ in range(m):
        v = int(data[index])
        p = int(data[index+1])
        q = int(data[index+2])
        items.append((v, p, q))
        index += 3
    
    # 获得最大满意度
    result = max_satisfaction(N, m, items)
    print(result)

# 读取输入并处理
if __name__ == "__main__":
    input_data = input()
    process_input(input_data)