BACKPACK - Dab of Backpack

One day Blue Mary goes to a nearby supermarket to buy some goods. She has a backpack, whose capacity is V-Max. She finds that there are many goods in the market, each has a volume Vi(it will always be a multiple of 10 and less than 10000) and an importance Ci (1<= Ci <=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 space-separated integers V-Max (1<=V-Max<=32000) and the number of the goods N (1<=N<=60). N lines follow, each contains three space-separated integers Vi, Ci 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

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

hide comments
2016-01-22 21:50:19 screw_1011
Test Case :
1
1000 2
100 1 2
100 3 0
Correct output : 400
2015-11-06 10:57:15 Shashank Tiwari
Here are some pointers :

1. Answer will be in int . U can see from question also. (5*32000 will be max what we will get).
2. Attachments can come before Main goods.
3. If I say '5 3 19' on any line of input , it means that it is an attachment to the good on 19th line of input (where Vi , Ci ,Ui starts getting inputted ... ) and these lines are 1 Indexed .

So , input can be like :

1
500 5
34 2 3
12 1 0
45 3 0
2 4 2
1 1 0
33 1 8
1 4 0
1 1 0
6 5 2
2015-08-16 08:34:45
Which approach is expected? Bottom-up, by this we mean that an accessory has been included now just add its parent object. Or, top-down 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?
2015-08-11 14:17:11 Nitesh Tiwari
Question: Assume that the value of the main product is zero.
But it has attachments which if added, will drastically increase the value of the bundle together.
In this case should I include the main products or not ?
2015-03-30 18:02:22 Malfple
Double Knapsack!
2015-02-23 18:12:56 priya choudhary
Attachments of any main good will be just after its main good or i/p can be like
2000 4
1000 2 0
1000 2 1
1000 2 0
1000 2 1
1000 5 3

Last edit: 2015-02-23 18:13:50
2015-02-04 16:26:55 rush
Nice problem :)
@californiagurl - You can't take any attachment more than once because you are given every item only once. Taking more than one instance of an item does not make any sense.
2015-02-03 21:33:08 do_do
finally accepted . Must to do DP problem ..
2015-02-03 15:02:15 californiagurl
so we can take each main item only once, but what about the attachments?
please clarify if a particular attachment can be taken more than once
2015-01-18 12:25:23 aditi
Can anyone please give some testcases...getting WA :(
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.