题目描述

华东师范0J 1244

太空梯的建造计划从一开始就引来了魔法界各派人物喋喋不休的争吵。 各派从学术观点、历史观点、美学观点等各方面引经据典,争论得面红耳赤。后来， 为了检验各派理论的正确性,项目主持者设计了一种积木游戏。每个游戏者有$\red{N}$ 块编号依次为$\red{1,2,...,N}$的长方体积木。对于每块积木，它的三条不同的边分别 称为"$\red{a}$边"、"$\red{b}$边"和"$\red{c}$边"，如图所示。

游戏规则如下:

$\red{(1)}$从$\red{N}$块积木中选出若干块，并将它们分成 $\red{M(1≤}$$\red{M≤}$$\red{N)}$堆,称为第$\red{1}$堆,第$\red{2}$堆,...,第$\red{M}$堆。每堆至 少有$\red{1}$块积木,并且第$\red{K}$堆中任意一块积木的编号要大于 第$\red{K+1}$堆中任意一块积木的蝙号$\red{(2≤}$$\red{K≤}$$\red{M)}$。

$\red{(2)}$对于每一堆积木,游戏者要将它们垂直摞成一根柱子,并要求满足下面两 个条件:

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

对于任意两块上下表面相接触的积木，下面的积木的编号要小于上面的积 木的编号。

最后,根据每人所摞成的$\red{M}$根柱子的高度之和来决出胜负。

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

输入格式

文件的第一行有两个正整数$\red{N}$和$\red{M(1≤}$$\red{M≤}$$\red{N≤}$$\red{100),}$分别表示积木总数和 要求摞成的柱子数。这两个数之间用一个空格符隔开。接下来$\red{N}$行依次是编号. 从$\red{1}$到$\red{N}$的$\red{N}$个积木的尺寸,每行有$\red{3}$个; $\red{1}$至$\red{1000}$之间的整数，分别表示该积 木$\red{a}$边,$\red{b}$边和$\red{c}$边的长度。同一行相邻两个数之间用一个空格符隔开。

输出格式

只有一行，为一个整数,表示$\red{M}$根柱子的高度之和。

样例

输入样例

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

输出样例

24