BACKPACK  Dab of Backpack
One day Blue Mary goes to a nearby supermarket to buy some goods. She has a backpack, whose capacity is VMax. She finds that there are many goods in the market, each has a volume V_{i}(it will always be a multiple of 10 and less than 10000) and an importance C_{i}(1<= C_{i} <=5). Since she has almost unlimited money, the only problem she is to solve is how to choose goods such that the total volume won't exceed the capacity of the backpack and the sum of the product of the volume and the importance of each good is maximum. To be an excellent mathematician, she comes up with the answer quickly, and now she wants you to do a harder task. There are two kinds of goods: main goods and attachments. If you want to buy an attachment you must buy its main good before.
Input
Multiple test cases, the number of them is given in the very first line.
For each test case:
The first line contains two spaceseparated integers VMax (1<=VMax<=32000) and the number of the goods N (1<=N<=60). N lines follow, each contains three spaceseparated integers V_{i}, C_{i} and a integer u. If u is not 0, this good is an attachment of good u(as the order in the input file).
To make the problem not too difficult, Blue Mary tells you that:
(A) An attachment won't have any attachments which belong to it.
(B) A main good will always have less than 3 attachments.
Output
For each test case:
The first and the only line contains a single integer denoted the answer.
Example
Input: 1 1000 5 800 2 0 400 5 1 300 5 1 400 3 0 500 2 0 Output: 2200
hide comments
surajkumar_cse:
20181226 15:02:47
They must provide other test cases which includes attachments first and then its main product.


hello_world123:
20180615 10:23:27
Use memoization Last edit: 20180615 10:23:47 

vengatesh15:
20170214 09:52:05
Took me 2 hours but easy one... Last edit: 20170214 09:52:53 

screw_1011:
20160122 21:50:19
Test Case :


Shashank Tiwari:
20151106 10:57:15
Here are some pointers :


pritishyuvraj:
20150816 08:34:45
Which approach is expected? Bottomup, by this we mean that an accessory has been included now just add its parent object. Or, topdown where where we keep selecting objects if an object is an accessory, check for its parent if it is not included simply add it. Or some other approach is expected? 

Nitesh Tiwari:
20150811 14:17:11
Question: Assume that the value of the main product is zero.


Malfple:
20150330 18:02:22
Double Knapsack! 

priya choudhary:
20150223 18:12:56
Attachments of any main good will be just after its main good or i/p can be like


rush:
20150204 16:26:55
Nice problem :)

Added by:  Fudan University Problem Setters 
Date:  20071103 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: C99 ERL JSRHINO 
Resource:  Based on a Problem from Chinese National Olympiad in Informatics in Province 2006 