Some days back Me and my Ex went 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(in between 1 and 5 both inclusive).

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.

And like always she wants me to do the computation and maximize the net worth, that is sum of the products of the volume and importance of goods.
There are two kinds of goods: main goods and attachments. If she wants to take an attachment she 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 and the number of the goods N. 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, She tells me that:
(A) An attachment won't have any attachments which belong to it.
(B) A main good will always have less than 3 attachments.

Constraints
1<=V-Max<=32000
1<=N<=60
10<=Vi<=10000
1<=Ci<=5

OUTPUT

For each test case:
The first and the only line contains a single integer denoting the answer that is the net woth sum of product of volume and importance.

Sample Input

`41000 5800 2 0400 5 1300 5 1400 3 0500 2 01000 2100 1 01000 5 11000 5400 5 0500 5 1300 4 0100 2 3200 1 01000 5400 5 0500 1 1300 4 0100 2 3200 1 0`

Sample Output

`220010045003600`

Vivek Keshri

Languages: C,C++,Java

Time Limit: 1 Second(s)
Score: 100 Point(s)
Input File Limit: 50000 Bytes

Mode Judge

RankNameScore
1xyz0
2Ams0
3TIP0
4team420
5xyzz0
6asdasdasd0
7abcd0
8khankhan0
9Gabriel0
10gigel0