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₁, Pile₂ ... Pile_M. There is at least 1 cuboid in each pile. To make the game easier, for any cuboid in Pile_K, its id should be 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 lesser 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