BRCKGAME  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 Pile_{1},Pile_{2} ... Pile_{M}. There are at least 1 cuboid in each pile. To make the game easier, for any cuboid in Pile_{K},its id should greater than any one in Pile_{K+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 Sample Output: 24
hide comments
:D:
20100304 12:38:59
They can be rotated. 

Luke Pebody:
20100302 18:09:50
Can the cuboids be rotated? Or are they given with height first? 
Added by:  Fudan University Problem Setters 
Date:  20070401 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: C99 ERL JSRHINO 
Resource:  Chinese National Olympiad in Informatics 1997,Day 2; translated by Blue Mary 