/ 
実行時間制限: 3 sec / メモリ制限: 1024 MiB
配点 : 625 点
問題文
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 個のテストケースが与えられるので、それぞれについて答えを求めてください。
制約
- 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
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
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 番目のテストケースに対する答えを出力せよ。
入力例 1
1 3 1 6 3 8 3 5 0 2 7 3
出力例 1
12
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 を出力します。
入力例 2
2 5 2 1 2 3 1 2 3 1 2 3 1 2 3 100 100 200 6 2 21 74 25 44 71 80 46 28 96 1 74 24 81 83 16 55 31 1
出力例 2
209 333
それぞれのケーキは高々 1 つのペアにしか含むことができないことに注意してください。
また、異なる種類のケーキであっても、綺麗さ、おいしさ、人気度がすべて等しい場合もあることに注意してください。
1 つめのテストケースについては、ケーキ 1 とケーキ 2 をペアにしたときの価格は 6、ケーキ 3 とケーキ 5 をペアにしたときの価格は 203 であり、これら 2 つのペアを選んだとき価格の合計は 209 となりこのときが最大です。
2 つめのテストケースについては、ケーキ 2 とケーキ 3 をペアにしたときの価格は 176、ケーキ 4 とケーキ 5 をペアにしたときの価格は 157 であり、これら 2 つのペアを選んだとき価格の合計は 333 となりこのときが最大です。
Score : 625 points
Problem Statement
Takahashi, a patissier working at the ABC pastry shop, decided to sell assorted cakes to commemorate AtCoder Beginner Contest 400.
The shop sells N kinds of cakes: cake 1, cake 2, \ldots, cake N.
Each cake has three non-negative integer values: beauty, tastiness, and popularity. Specifically, cake i has beauty X_i, tastiness Y_i, and popularity Z_i.
He considers pairing up these cakes into K pairs without overlaps.
Formally, he will choose 2K distinct integers a_1,b_1,a_2,b_2,\ldots,a_K,b_K between 1 and N (inclusive), and pair cake a_i with cake b_i.
The price of a pair formed by cakes a_i and b_i is \max(X_{a_i} + X_{b_i},\, Y_{a_i} + Y_{b_i},\, Z_{a_i} + Z_{b_i}).
Here, \max(P,Q,R) denotes the greatest value among P,Q,R.
Find the maximum possible total price of the K pairs.
You are given T test cases; solve each of them.
Constraints
- 1\leq T\leq 1000
- 2\leq N \leq 10^5
- The sum of N over all test cases in each input file is at most 10^5.
- 1\leq K \leq \lfloor \frac{N}{2}\rfloor (For a real number x, \lfloor x\rfloor denotes the greatest integer not exceeding x.)
- 0\leq X_i,Y_i,Z_i \leq 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
\mathrm{case}_i represents the i-th test case. Each test case is given in the following format:
N K X_1 Y_1 Z_1 X_2 Y_2 Z_2 \vdots X_N Y_N Z_N
Output
Print T lines. The i-th line (1\leq i\leq T) should contain the answer to the i-th test case.
Sample Input 1
1 3 1 6 3 8 3 5 0 2 7 3
Sample Output 1
12
We form one pair out of three cakes.
If we pair cake 1 with cake 2, the price is \max(6+3,\,3+5,\,8+0) = 9.
If we pair cake 1 with cake 3, the price is \max(6+2,\,3+7,\,8+3) = 11.
If we pair cake 2 with cake 3, the price is \max(3+2,\,5+7,\,0+3) = 12.
Hence, pairing cake 2 with cake 3 gives the highest price, which is 12.
Sample Input 2
2 5 2 1 2 3 1 2 3 1 2 3 1 2 3 100 100 200 6 2 21 74 25 44 71 80 46 28 96 1 74 24 81 83 16 55 31 1
Sample Output 2
209 333
Note that each cake can appear in at most one pair.
Also note that there can be different cakes with identical values of beauty, tastiness, and popularity.
For the first test case, pairing cake 1 with cake 2 gives a price of 6, pairing cake 3 with cake 5 gives a price of 203, and choosing these two pairs yields a total price of 209, which is the maximum.
For the second test case, pairing cake 2 with cake 3 gives a price of 176, pairing cake 4 with cake 5 gives a price of 157, and choosing these two pairs yields a total price of 333, which is the maximum.