分数: 625 点
问题陈述
在 ABC 糕点店工作的糕点师 Takahashi 决定出售什锦蛋糕来纪念 AtCoder 初学者大赛 400。
本店有售 N 蛋糕种类: 蛋糕 1,蛋糕 2, \ldots,蛋糕 N.
每个蛋糕都有三个非负整数值:美观度、美味度和受欢迎度。具体来说,蛋糕 i 有美 X_i,美味 Y_i和受欢迎程度 Z_i.
他考虑将这些蛋糕搭配成 K 配对无重叠。
正式地,他将选择 2K 不同 整数 a_1,b_1,a_2,b_2,\ldots,a_K,b_K 之间 1 和 N (含)和配对蛋糕 a_i 有蛋糕 b_i.
蛋糕组成的一对的价格 a_i 和 b_i is \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 T) 应包含以下问题的答案 i- 第一个测试用例。
示例输入 1
1 3 1 6 3 8 3 5 0 2 7 3
示例输出 1
12
我们从三个蛋糕中组成一对。
如果我们配对蛋糕 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 有蛋糕 2 给出的价格为 6,配对蛋糕 3 有蛋糕 5 给出的价格为 203,选择这两对的总价格为 209,这是最大值。
对于第二个测试用例,配对蛋糕 2 有蛋糕 3 给出的价格为 176,配对蛋糕 4 有蛋糕 5 给出的价格为 157,选择这两对的总价格为 333,这是最大值。