题目描述

SERCOI 最近设计了一种积木游戏。每个游戏者有 $n$ 块编号依次为 $1,2,...,n$ 的长方体积木。对于每块积木，它的三条不同的边分别称为 $a$ 边、$b$ 边和 $c$ 边，如下图所示：

游戏规则如下：

1. 从 $n$ 块积木中选出若干块，并将它们分成 $m$（$1 \le m \le n$）堆，称为第 $1$ 堆，第 $2$ 堆 ...，第 $m$ 堆。每堆至少有 $1$ 块积木，并且第 $k$ 堆中任意一块积木的编号要大于第 $k+1$ 堆中任意一块积木的编号（$2 \le k \le m$）。

2. 对于每一堆积木，游戏者要将它们垂直摞成一根柱子，并要求满足下面两个条件：

   • 除最顶上的一块积木外，任意一块积木的上表面同且仅同另一块积木的下表面接触，并且要求下面的积木的上表面能包含上面的积木的下表面，也就是说，要求下面的积木的上表面的两对边的长度分别大于等于上面的积木的两对边的长度。
   • 对于任意两块上下表面相接触的积木，下面的积木的编号要小于上面的积木的编号。

最后，根据每人所摞成的 $m$ 根柱子的高度之和来决出胜负。

请你编一程序，寻找一种摞积木的方案，使得你所摞成的 $m$ 根柱子的高度之和最大。

输入格式

一行有两个正整数 $n$ 和 $m$（$1 \le m \le n \le 100$），分别表示积木总数和要求摞成的柱子数。这两个数之间用一个空格符隔开。

接下来 $n$ 行依次是编号从 $1$ 到 $n$ 的 $n$ 个积木的尺寸，每行有三个 $1$ 至 $1000$ 之间的整数，分别表示该积木 $a$ 边，$b$ 边和 $c$ 边的长度。同一行相邻两个数之间用一个空格符隔开。

输出格式

只有一行，为一个整数，表示 $m$ 根柱子的高度之和的最大值。

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

24