BRCKGAME - A Game of Toy Bricks

no tags 

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

Sample Output:
24

hide comments
:D: 2010-03-04 12:38:59

They can be rotated.

Luke Pebody: 2010-03-02 18:09:50

Can the cuboids be rotated? Or are they given with height first?


Added by:Fudan University Problem Setters
Date:2007-04-01
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: C99 ERL JS-RHINO
Resource:Chinese National Olympiad in Informatics 1997,Day 2; translated by Blue Mary