2120: 宝典2第十一章积木游戏

【题目描述】积木游戏(juggle.cpp/c/pas)华东师范OJ 1244 

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

游戏规则如下：

（１）从N块积木中选出若干块，并将它们分成M（l≤M≤N） 堆，称为第1堆，第2 堆，…，第M堆。每堆至少有1块积木，并且第K堆中任意一块积木的编号要大于第K+1堆中任意一块积木的编号(2≤K≤M)。

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

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

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

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

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

【输入格式】

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

【输出格式】

只有一行，为一个整数，表示M根柱子的高度之和。

【输入样例】

4 2

10 5 5

8 7 7

2 2 2

6 6 6

【输出样例】

24