PEG Judge - NOI '97 - Building Game

National Olympiad in Informatics, China, 1997

Day 2, Problem 2 - Building Game

SERCOI has recently designed a game with building block. Each player has N wooden blocks (with IDs assigned from 1 to N) in the shape of rectangular prisms. For every block, its three distinct sides are respectively known as "side a", "side b" and "side c", as shown in the figure below:

The rules of the game are as follows:

Each player selects some number of blocks from their N total blocks, and splits them up into M (1 ≤ M ≤ N) piles which we will call pile 1, pile 2, …, pile M. Each pile must have at least 1 block, and the ID of any block in the k-th pile must be greater than the ID of any block in the (k−1)-th pile (for 2 ≤ k ≤ M).
For each pile of blocks, the player must arrange them into a stack under the following two conditions:
- Other than the top-most block in the stack, the top surface of every block must be touching the bottom surface of another block. Additionally, for every pair of touching blocks, the top block's bottom surface must be fully contained in the bottom block's top surface. In other words, the dimensions of the bottom block's top surface must be larger than or equal to the corresponding dimensions of the top block's bottom surface.
- For every pair of touching blocks, the ID of the lower block must be smaller than than the ID of the upper block.

At the end, the winner is determined from the heights of each player's M stacks. Please write a program that finds a strategy for stacking blocks such that the sum of the heights of the M stacks are maximized.

Input Format

The first line of input contains two space-separated integers N and M (1 ≤ M ≤ N ≤ 100), the number of blocks and the number of stacks to build, respectively. The next N lines each contain three side lengths a, b, and c, each an integer from 1 to 1000, describing the dimensions of the N blocks.