← 返回题目列表

AtCoder · abc400_g

G. 糕点店 ABC 3

中文机器翻译题面 查看原题

分数: 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,这是最大值。