SP1447 BRCKGAME - A Game of Toy Bricks

Blue Mary 发明了一款使用积木块进行的游戏。玩家手中有 $N$ 个编号从 $1$ 到 $N$ 的长方体。 游戏规则如下： - 从这 $N$ 个长方体中选择一些，并将它们分成 $M$ 堆（$1 \le M \le N$），分别称为第 $1$ 堆、第 $2$ 堆直到第 $M$ 堆。每堆至少包含一个长方体。为简化游戏，任何在第 $K$ 堆中的长方体，其编号都应该大于在第 $K+1$ 堆中的任意长方体的编号（$1 \le K < M$）。 - 每堆中的长方体需要被堆叠成一个塔，并且需满足以下条件： - 每个长方体的上表面只会接触另一个长方体的下表面。为了让堆叠看起来像座塔，下面的长方体的上表面长度和宽度必须至少等于上面长方体的下表面长度和宽度。 - 在每一堆内，更低的长方体的编号要小于更高的长方体的编号。

第一行包含一个整数 $t$，表示测试用例的数量。接下来有 $t$ 组测试用例。 每个测试用例的第一行包含两个整数 $N$ 和 $M$，用空格分隔。$N$（$N \leq 100$）是长方体的总数量，$M$（$M \leq N$）是要分成的堆数。 接下来的 $N$ 行描述了从编号为 $1$ 到 $N$ 的长方体。每行包含三个整数（ $\leq 1000$）——表示该长方体的长度、宽度和高度，数值之间用空格分隔。

对于每个测试用例，输出一行，内容为一个整数，表示最大的总高度。

- $1 \leq t \leq 10$ - $1 \leq N \leq 100$ - $1 \leq M \leq N$ - $1 \leq \text{长度, 宽度, 高度} \leq 1000$ 请根据给出的输入格式和要求进行作答。 **本翻译由 AI 自动生成**