Description

SERCOI has recently designed a block game. Each player has $N$ rectangular blocks numbered $1, 2, \ldots, N$. For each block, its three different edges are called the "a edge", "b edge", and "c edge", as shown in the figure below:

The rules are as follows:

1. Choose some blocks from the $N$ blocks and divide them into $M$ ($1 \le M \le N$) piles, called pile $1$, pile $2$, $\ldots$, pile $M$. Each pile must contain at least $1$ block, and for pile $K$, the number of any block in pile $K$ must be greater than the number of any block in pile $K+1$ ($2 \le K \le M$).

2. For each pile, the player stacks the blocks vertically into a single column, and it must satisfy the following two conditions:

$\qquad$ 1) Except for the top block, the top face of any block must touch one and only one other block’s bottom face. Also, the top face of the lower block must be able to contain the bottom face of the upper block. That is, the lengths of the two pairs of edges on the top face of the lower block must each be greater than or equal to the corresponding two pairs of edges on the bottom face of the upper block.

$\qquad$ 2) For any two blocks whose top and bottom faces are in contact, the number of the lower block must be smaller than the number of the upper block.

Finally, the winner is determined by the sum of the heights of the $M$ columns.

Please write a program to find a stacking plan such that the sum of the heights of the $M$ columns is maximized.

Input Format

The first line contains two positive integers $N$ and $M$ ($1 \le M \le N \le 100$), representing the total number of blocks and the required number of columns. The two numbers are separated by a space.

The next $N$ lines give the sizes of the $N$ blocks numbered from $1$ to $N$ in order. Each line contains three integers between $1$ and $1000$, representing the lengths of the a edge, b edge, and c edge of that block. Adjacent numbers on the same line are separated by a space.

Output Format

Only one line containing one integer, which is the maximum possible sum of the heights of the $M$ columns.

4 2
10 5 5
8 7 7
2 2 2
6 6 6

24

Hint

Translated by ChatGPT 5