AT_abc400_g.[ABC400G] Patisserie ABC 3

在 ABC 西点店工作的糕点师高桥君决定为纪念 AtCoder Beginner Contest 400 推出特别蛋糕套装。

ABC 西点店销售 $N$ 种蛋糕，分别为蛋糕 $1$，蛋糕 $2$，……，蛋糕 $N$。
每个蛋糕具有三个非负整数值属性：美观度、美味度和人气度。具体来说，蛋糕 $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 T$）应输出第 $i$ 个测试用例的答案。

约束条件

• $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$
• 输入中的所有值均为整数

样例解释 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$。

样例解释 2

注意每个蛋糕最多只能出现在一个对中。此外，即使不同种类的蛋糕，其美观度、美味度、人气度也可能完全相同。
对于第一个测试用例，选择蛋糕 $1$ 和 $2$（价格 $6$）以及蛋糕 $3$ 和 $5$（价格 $203$），总价格为 $209$。
对于第二个测试用例，选择蛋糕 $2$ 和 $3$（价格 $176$）以及蛋糕 $4$ 和 $5$（价格 $157$），总价格为 $333$。

翻译由 DeepSeek R1 完成