AT_abc400_g [ABC400G] Patisserie ABC 3

ABC 洋菓子店で働くパティシエである高橋君は、AtCoder Beginner Contest 400 を記念したケーキのセットを販売することにしました。 ABC 洋菓子店にはケーキ $ 1 $ , ケーキ $ 2 $ , $ \ldots $ , ケーキ $ N $ の $ N $ 種類のケーキが販売されています。 各ケーキは綺麗さ、おいしさ、人気度の $ 3 $ つの非負整数値を持ち、 具体的にはケーキ $ i $ の綺麗さ、おいしさ、人気度はそれぞれ $ X_i,Y_i,Z_i $ です。 高橋君はケーキを被りのない $ K $ 個のペアにして売り出すことを考えました。 形式的に説明すると、 $ 2K $ 個の **相異なる** $ 1 $ 以上 $ N $ 以下の整数 $ a_1,b_1,a_2,b_2,\ldots,a_K,b_K $ を選んでケーキ $ a_i $ とケーキ $ b_i $ をペアにすることにしました。 ケーキ $ a_i $ とケーキ $ b_i $ をペアにした時のペアの価格は $ \max(X_{a_i}+X_{b_i}, Y_{a_i}+Y_{b_i}, Z_{a_i}+Z_{b_i}) $ とします。 ただし、 $ \max(P,Q,R) $ で $ P,Q,R $ のうち最大の値を表します。 $ K $ 個のペアの価格の総和としてあり得る最大の値を求めてください。 $ T $ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ $ \mathrm{case}_i $ は $ i $ 番目のテストケースを表す。 各テストケースは以下の形式で与えられる。 > $ N $ $ K $ $ X_1 $ $ Y_1 $ $ Z_1 $ $ X_2 $ $ Y_2 $ $ Z_2 $ $ \vdots $ $ X_N $ $ Y_N $ $ Z_N $

$ T $ 行出力せよ。 $ i $ 行目 $ (1\leq i\leq N) $ には $ i $ 番目のテストケースに対する答えを出力せよ。

### Sample Explanation 1 $ 3 $ つのケーキから $ 1 $ つのペアを作ります。 ケーキ $ 1 $ とケーキ $ 2 $ をペアにした時の価格は $ \max(6+3,3+5,8+0)=9 $ です。 ケーキ $ 1 $ とケーキ $ 3 $ をペアにした時の価格は $ \max(6+2,3+7,8+3)=11 $ です。 ケーキ $ 2 $ とケーキ $ 3 $ をペアにした時の価格は $ \max(3+2,5+7,0+3)=12 $ です。 よってケーキ $ 2 $ とケーキ $ 3 $ をペアにした時の価格が最大であり、 $ 12 $ を出力します。 ### Sample Explanation 2 それぞれのケーキは高々 $ 1 $ つのペアにしか含むことができないことに注意してください。 また、異なる種類のケーキであっても、綺麗さ、おいしさ、人気度がすべて等しい場合もあることに注意してください。 $ 1 $ つめのテストケースについては、ケーキ $ 1 $ とケーキ $ 2 $ をペアにしたときの価格は $ 6 $ 、ケーキ $ 3 $ とケーキ $ 5 $ をペアにしたときの価格は $ 203 $ であり、これら $ 2 $ つのペアを選んだとき価格の合計は $ 209 $ となりこのときが最大です。 $ 2 $ つめのテストケースについては、ケーキ $ 2 $ とケーキ $ 3 $ をペアにしたときの価格は $ 176 $ 、ケーキ $ 4 $ とケーキ $ 5 $ をペアにしたときの価格は $ 157 $ であり、これら $ 2 $ つのペアを選んだとき価格の合計は $ 333 $ となりこのときが最大です。 ### Constraints - $ 1\leq T\leq 1000 $ - $ 2\leq N \leq 10^5 $ - 各入力ファイルについて、すべてのテストケースの $ N $ の総和は $ 10^5 $ 以下である。 - $ 1\leq K \leq \lfloor \frac{N}{2}\rfloor $ （実数 $ x $ に対し、 $ \lfloor x\rfloor $ で $ x $ 以下の最大の整数を表す。） - $ 0\leq X_i,Y_i,Z_i \leq 10^9 $ - 入力はすべて整数