Formation Of Idol Unit

問題文

処理犬君は、998 プロダクションというアイドル事務所のプロデューサーです。
その事務所には $N$ 人にアイドルが在籍しており、それぞれ以下の三つのステータスが正整数で定められています。

• Vi（Visual：風貌）
• Da（Dance：踊り）
• Vo（Vocal：歌唱力）

$i \, (1 \leq i \leq N)$ 番目のアイドルの「Vi」は $A_i$ 、 「Da」は $B_i$ 、 「Vo」は $C_i$ です。

処理犬君は、そのアイドル事務所の高林社長から、以下のような依頼を受けました。

• 事務所に所属するアイドルの中からちょうど $M$ 人を選んで、アイドルユニットを新たに作ってほしい。
• $M$ 人を選ぶ際には、以下のように定義されるユニットの「魅力度」を最大化するように $M$ 人を選び、そのときの「魅力度」の値を報告して欲しい 。

ユニットの魅力度

1. ユニットに含まれるアイドルの、「Vi」ステータスの集合を $S_{Vi}$ 、「Da」ステータスの集合を $S_{Da}$ 、「Vo」ステータスの集合を $S_{Vo}$ とする。
2. このとき、ユニットの「魅力度」は次の式で定義される。

処理犬君は早速この仕事に取り掛かりましたが、「魅力度」を最大化するように $M$ 人を選んだときの 「魅力度」を求めることができず、困っています。
処理犬君を助けるために、「魅力度」を最大化するように $M$ 人を選んだときのユニットの「魅力度」の値を出力するプログラムを書いてください。

制約

• $1 \leq N \leq 10^5$
• $1 \leq M \leq N$
• $1 \leq A_i \leq 10^9 \, (1 \leq i \leq N)$
• $1 \leq B_i \leq 10^9 \, (1 \leq i \leq N)$
• $1 \leq C_i \leq 10^9 \, (1 \leq i \leq N)$
• 入力は全て整数

入力

N M
A_1 B_1 C_1
A_2 B_2 C_2
...
...
A_N B_N C_N

• $1$ 行目に所属するアイドルの数 $N$ 、新たに作るユニットの人数 $M$ が与えられます。
• $2$ 行目以降に各アイドルのステータスが与えられます。

出力

「魅力度」を最大化するように $M$ 人を選んだときのユニットの「魅力度」の値を出力してください。

入力例 1

5 2
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2

出力例 1

8

例えば、 $1$ 番目のアイドルと、 $5$ 番目のアイドルを選ぶと、それぞれのステータス (Vi,Da,Vo) は、$(1, 2, 3),(3, 1, 2)$ です。
ユニットに含まれるアイドルの、「Vi」ステータスの集合を $S_{Vi}$ 、「Da」ステータスの集合を $S_{Da}$ 、「Vo」ステータスの集合を $S_{Vo}$ としたとき、それぞれは以下のようになります。

• $S_{Vi} = \{1,3\}$
• $S_{Da} = \{2,1\}$
• $S_{Vo} = \{3,2\}$

よって、ユニットの「魅力度」は
$\mathrm{max}(S_{Vi}) + \mathrm{max}(S_{Da}) + \mathrm{max}(S_{Vo}) = \mathrm{max}(\{1,3\}) + \mathrm{max}(\{2,1\}) + \mathrm{max}(\{3,2\}) = 3 + 2 + 3 = 8$ です。 ユニットの「魅力度」を $8$ より大きくする選び方は存在しないので、$8$ を出力します。

入力例 2

1 1
1 1 1

出力例 2

3

入力例 3

4 4
1 1 4
1 3 3
5 1 1
1 4 1

出力例 3

13