A Game of Toy Bricks
Blue Mary invents a game with toy bricks. The player has N cuboids numbered from 1 to N.
The rule of the game is discribed below:
- Choose some cuboids among the N cuboids, and divide them into M(1 <= M <= N) piles,named them Pile1,Pile2 ... PileM. There are at least 1 cuboid in each pile. To make the game easier, for any cuboid in PileK,its id should greater than any one in PileK+1 (1 <= K < M).
- For each pile of cuboids,the player will put them as a tower, and he should follow the two rules below:
- The up surface of each cuboid is touched and only touched another down surface. Luckily,to make the pile looking like a tower,the up surface of the lower cuboid should cover the down surface of the higher cuboid,i.e. the length of the lower up surface is not less than that of the higher down surface, and also to the width.
- In each pile,the lower cuboid has a less id than the higher cuboid.
Your task is to find a method,to make the sum of the height of each pile maximum.
Input
The very first line of the input contain the number t,then t cases follow.
For each case,The first line contain two integer number N and M. N(N<=100) is the total number of the cuboids, M(M<=N) is the number of the piles, separated by a single space.
Then N line follow, which are the description of the cuboids 1..N. Each line contains three integer numbers(<=1000)- the length, width and height of that cuboid,separated by spaces.
Output
For each case, the output contains only one line with a single integer number - the maximum sum.
Example
Sample Input: 1 4 2 10 5 5 8 7 7 2 2 2 6 6 6</p>Sample Output: 24