题解 | 购物单

import sys


def main():
    # 1. 读取预算n和物品数m，预算÷10简化计算
    n, m = map(int, sys.stdin.readline().split())
    n //= 10  # 简化后预算单位：10元/单位

    # 存储主件及对应附件：主件列表格式为 (主件v, 主件val, 附件列表)
    master_list = []
    # 临时字典：key=主件ID，value=主件的附件列表（先初始化主件，再填附件）
    att_map = dict()

    # -------------------------- 第一步：先读取所有物品，仅初始化主件 --------------------------
    # 先存储所有物品的原始数据（避免二次读入），格式：(v, val, q, item_id)
    all_items = []
    for item_id in range(1, m + 1):
        v, w, q = map(int, sys.stdin.readline().split())
        v //= 10  # 价格简化
        val = v * w  # 满意度
        all_items.append((v, val, q, item_id))

    # 遍历所有物品，先初始化主件（q=0），确保att_map中有所有主件ID
    for v, val, q, item_id in all_items:
        if q == 0:
            attachments = []  # 初始化该主件的空附件列表
            master_list.append((v, val, attachments))
            att_map[item_id] = attachments  # 主件ID存入att_map，绑定附件列表

    # -------------------------- 第二步：再遍历所有物品，处理附件（q≠0） --------------------------
    for v, val, q, item_id in all_items:
        if q != 0:
            # 此时q（主件ID）已在第一步初始化，att_map[q]必然存在
            att_map[q].append((v, val))

    # 3. 初始化DP数组：dp[j] = 简化后预算j时的最大满意度
    dp = [0] * (n + 1)

    # 4. 遍历每个主件，枚举所有合法策略（适配≤2个附件）
    for main_v, main_val, attachments in master_list:
        # 提前提取附件（最多2个），避免重复索引
        a1_v, a1_val = (0, 0) if len(attachments) < 1 else attachments[0]
        a2_v, a2_val = (0, 0) if len(attachments) < 2 else attachments[1]

        # 逆序遍历预算（至少覆盖主件价格）
        for j in range(n, main_v - 1, -1):
            # 策略1：只买主件
            dp[j] = max(dp[j], dp[j - main_v] + main_val)

            # 策略2：主件 + 第一个附件
            if len(attachments) >= 1 and j >= main_v + a1_v:
                dp[j] = max(dp[j], dp[j - main_v - a1_v] + main_val + a1_val)

            # 策略3：主件 + 第二个附件
            if len(attachments) >= 2 and j >= main_v + a2_v:
                dp[j] = max(dp[j], dp[j - main_v - a2_v] + main_val + a2_val)

            # 策略4：主件 + 两个附件
            if len(attachments) >= 2 and j >= main_v + a1_v + a2_v:
                dp[j] = max(
                    dp[j], dp[j - main_v - a1_v - a2_v] + main_val + a1_val + a2_val
                )

    # 5. 还原预算单位，输出结果
    print(dp[n] * 10)


if __name__ == "__main__":
    main()