01背包动态规划的递归解法，自己想了很久，没参考任何人的答案，但不幸的是会超时或者超空间，毕竟也是辛苦想出来的解法还是写一下。如果有改进意见的欢迎指正。

import functools
n, m = map(int, input().split())
price = []
content = []
nums = []
#输入数据处理
for line in range(m):
    a = input().split()
    price.append(int(a[0]))
    content.append(int(a[1]))
    nums.append(int(a[2]))

best = 0 # 计算公式为所购物品各自的价格×满意度之和
@functools.lru_cache(maxsize=None) #内存装饰器，按理可以缩短时间节省内存，但这里好像并没有什么帮助，仍然超时
def dfs(money, i, mask, scores, l):
    global best
    if money <= 0 or i == l:
        return
    if not mask & (1<<i) and money >= price[i]:#如果该物品不在清单并且剩余的钱够买
        if nums[i] == 0 or (nums[i] != 0 and mask & (1<<(nums[i]-1))):#如果是主体，或者不是主体并且其主体已经在购物单里，只需购买这一件
            m = money - price[i]
            new_mask = mask | (1<<i)
            sc = scores
            sc += price[i]*content[i]
            best = max(best, sc)
            dfs(m, i + 1, new_mask, sc, l)
        elif  money - price[i] - price[nums[i]-1] >=0:#如果是附件，并且其主体也不在购物单里，剩余的钱也可以买两件，则买两件
            m = money - price[i] - price[nums[i]-1]
            new_mask = mask | (1<<i)
            new_mask = new_mask | (1<<(nums[i]-1))
            sc = scores
            sc += price[i]*content[i] + price[nums[i]-1]*content[nums[i]-1]
            best = max(best, sc)
            dfs(m, i + 1, new_mask, sc, l)
    dfs(money, i+1, mask, scores, l)
dfs(n, 0, 0, 0, m)
print(best)