describe
Wang Qiang is very happy today , The company issued N A year-end bonus of yuan . Wang Qiang decided to use the year-end bonus for shopping , He divided the items he wanted to buy into two categories ： Main parts and accessories , The attachment is subordinate to a main component , Here are some examples of main components and accessories ：
If you want to buy items classified as accessories , You must buy the main part of the accessory first . Each main component can have 0 individual 、 1 Or 2 Attachments . Attachments no longer have their own attachments . Wang Qiang wants to buy a lot of things , In order not to exceed the budget , He set an importance level for each item , It is divided into 5 etc. ： Integers 1 ~ 5 Express , The first 5 And so on . He also looked up the price of each item on the Internet （ All are 10 An integral multiple of one yuan ）. He hopes not to exceed N element （ Can be equal to N element ） Under the premise of , To maximize the sum of the product of the price of each item and its importance .
Set the first j The price of the item is v[j] , The importance is w[j] , A total of k Item , The serial numbers are j 1 , j 2 ,……, j k , Then the sum of the requirements is ：
v[j 1 ]*w[j 1 ]+v[j 2 ]*w[j 2 ]+ … +v[j k ]*w[j k ] .（ among * For the multiplier ）
Please help Wang Qiang design a shopping list that meets the requirements .
Input description ：
Input the 1 That's ok , For two positive integers , Separated by a space ：N m
（ among N （ <32000 ） It means the total amount of money , m （ <60 ） For the number of items you want to buy .）
From 2 Go to the first place m+1 That's ok , The first j Line gives the number j-1 The basic data of the items , Each row has 3 Nonnegative integers v p q
（ among v Indicates the price of the item （ v<10000 ）, p Indicates the importance of the item （ 1 ~ 5 ）, q Indicates whether the item is a master or an accessory . If q=0 , It means that the article is the main component , If q>0 , It means that the article is an accessory , q Is the number of the main part ）
Output description ：
The output file has only one positive integer , It is the maximum value of the sum of the product of the price and importance of the goods that does not exceed the total amount of money （ <200000 ）.
Example 1
Input ：
1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0
Output ：
2200
Knapsack problem ：
Yes N Items and a capacity for V The backpack . The first i The weight of the item is w[i], The value is v[i]. Solve which items are loaded into the backpack so that the total weight of these items does not exceed the backpack capacity , And the sum of values is the largest .
The basic idea
This is the basic knapsack problem , Characteristic is ： There is only one item of each kind , You can choose to put it or not .
Define states with subproblems ： namely f[i][v] Before presentation i Items are just put into a capacity of v The maximum value that you can get from your backpack . Then the equation of state transfer is ：
f[i][v]=max{ f[i-1][v], f[i-1][v-w[i]]+v[i] }.
It can compress space ,f[v]=max{f[v],f[v-w[i]]+v[i]}
This equation is very important , Basically, the equations of all knapsack related problems are derived from it . So it is necessary to explain it in detail ：“ Before the i The capacity of items is v In my backpack ” This subproblem , If we only consider i Strategy of items （ With or without ）, Then it can be transformed into a front only i-1 Problems with items . If you don't put the first i Item , Then the problem turns into “ front i-1 The capacity of items is v In my backpack ”, Value is f[i-1][v]; If you put the first i Item , Then the problem turns into “ front i-1 Put items into the remaining capacity of v-w[i] In my backpack ”, The greatest value you can get at this time is f [i-1][v-w[i]] Plus by putting the i The value of items v[i].
Be careful f[v] Meaningful if and only if there is a pre i A subset of items , The total cost is f[v]. So after recursion according to this equation , The final answer is not necessarily f[N] [V], It is f[N][0..V] The maximum of . If the state is defined as “ just ” Remove the word , We have to add another term to the transfer equation f[v-1], So that's a guarantee f[N] [V] That's the final answer . As for why this can , It's up to you to experience .
Code implementation ：
n, m = map(int,input().split())
primary, annex = {}, {}
for i in range(1,m+1):
x, y, z = map(int, input().split())
if z==0:# Main parts
primary[i] = [x, y]
else:# The attachment
if z in annex:# The second attachment
annex[z].append([x, y])
else:# The first attachment
annex[z] = [[x,y]]
m = len(primary)# The number of main items is converted into the number of items
dp = [[0]*(n+1) for _ in range(m+1)]
w, v= [[]], [[]]
for key in primary:
w_temp, v_temp = [], []
w_temp.append(primary[key][0])#1、 Main parts
v_temp.append(primary[key][0]*primary[key][1])
if key in annex:# Existing master
w_temp.append(w_temp[0]+annex[key][0][0])#2、 Main parts + The attachment 1
v_temp.append(v_temp[0]+annex[key][0][0]*annex[key][0][1])
if len(annex[key])>1:# There are two main components
w_temp.append(w_temp[0]+annex[key][1][0])#3、 Main parts + The attachment 2
v_temp.append(v_temp[0]+annex[key][1][0]*annex[key][1][1])
w_temp.append(w_temp[0]+annex[key][0][0]+annex[key][1][0])#3、 Main parts + The attachment 1+ The attachment 2
v_temp.append(v_temp[0]+annex[key][0][0]*annex[key][0][1]+annex[key][1][0]*annex[key][1][1])
w.append(w_temp)
v.append(v_temp)
for i in range(1,m+1):
for j in range(10,n+1,10):# The price of the item is 10 Integer multiple
max_i = dp[i-1][j]
for k in range(len(w[i])):
if j-w[i][k]>=0:
max_i = max(max_i, dp[i-1][j-w[i][k]]+v[i][k])
dp[i][j] = max_i
print(dp[m][n])
