1.5.2
例題5
積木遊戯
n(n<=100)個の直方体の積木を持っている.積木にはそれぞれ1からn
までの番号がついている.
ここで,下図のように,積木の形を決定する３辺を,a辺,b辺,c辺と呼ぶことにする.
ゲームの規則は以下の通りである.
1. n個の積木をm(1<=k<=m)のグループに分ける.
それぞれのグループは少なくとも1個の積木を含み,第kグループ中にあるすべての積木のidは,第k-1グループにあるどの積木のidよりも大きい.
2. 以下の規則にしたがって,積木を垂直に並べて柱を作る.
 a. 最も上にある積木を除いて,ある積木とすぐ下にある積木の表面は接触していて,
かつ下の積木の接触面は上の積木の接触面を包含している.
別の言い方をすれば,下の長方形の2辺が,上の長方形の対応する2辺の長さ以上になる.
 b. 互いに接触する積木に関して,下にある積木のidは上にある積木のidより小さい.
3. できたm個の柱の高さの和を最大にする.

Input
入力は以下のように与えられる.
	n m
	a1 b1 c1
	a2 b2 c2
	a3 b3 c3
	...
	an bn cn
nは直方体の個数であり,mはグループの数である.(1<=m<=n)
ai,bi,ciはそれぞれi番目の直方体の各辺の長さである。(1<=ai,bi,ci<=1000)

Output
柱の高さの和の最大値を1行で出力しなさい.

Sample Input
4 2
10 5 5
8 7 7
2 2 2
6 6 6

Sample Output
24

出典:noi97