CF2275D Precision Alignment

K1o0n 志愿在物理系担任助教，他负责 $n$ 个实验室。在第 $i$ 个实验室中，有三台仪器，其读数分别为 $a_i$、$b_i$ 和 $c_i$。这些仪器是有区分的，三元组中的顺序是固定的：第一个为 $a_i$，第二个为 $b_i$，第三个为 $c_i$。 每次操作可以选择一个实验室 $i$，进行如下三种调整之一： - $c_i \mathrel{+}= \operatorname{sgn}(a_i - b_i)$ - $b_i \mathrel{+}= \operatorname{sgn}(a_i - c_i)$ - $a_i \mathrel{+}= \operatorname{sgn}(b_i - c_i)$ 其中，$\operatorname{sgn}(x)$ 表示符号函数，若 $x > 0$ 则等于 $1$，若 $x < 0$ 则等于 $-1$，若 $x = 0$ 则等于 $0$。 换句话说，每次操作会使某个仪器的读数变化 $1$ 个单位，变大的还是变小的由另外两个仪器读数的差决定，按给定顺序（前一个减去后一个）。 多个操作依次执行，每次操作均基于当时已经得到的最新读数。每个实验室可以多次操作，也可以完全不操作；K1o0n 总共最多只能进行 $k$ 次操作。 最终的工作表现将由最差实验室决定： $$ S = \min_{1 \le i \le n} (a_i + b_i + c_i) $$ 其中取的是所有操作结束后仪器的读数总和。K1o0n 想让同事们刮目相看，所以请你帮他计算，他能获得的最大 $S$ 是多少。

第一行包含一个整数 $t$（$1 \le t \le 10^4$）——表示测试用例的数量。 每个测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 2 \cdot 10^5$，$0 \le k \le 10^{18}$）——分别为实验室数量和最多允许的操作次数。 接下来每个测试用例输入 $n$ 行，每行含有三个整数 $a_i$、$b_i$、$c_i$（$-10^9 \le a_i, b_i, c_i \le 10^9$）。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一个整数，表示能够获得的最大 $S$。 注意，答案可能超出 32 位整型范围。请在 C++ 中使用 long long，在 Java 中使用 long。

在第一个测试用例中，若需要使所有三元组最小和为 $-2$，应将 $\operatorname{sgn}(b_1 - c_1) = 1$ 添加到 $a_1$ 上四次，此时三元组 $(a_1, b_1, c_1)$ 变为 $(1, -1, -2)$，其余三元组初始总和大于 $-2$。可以证明无法通过允许的操作次数使和达到 $-1$ 或以上。 在第二个测试用例中，若需使最小三元组和为 $14$，应将 $\operatorname{sgn}(b_1 - c_1)=1$ 添加到 $a_1$ 上 $2$ 次，将 $\operatorname{sgn}(a_2 - c_2)=1$ 添加到 $b_2$ 一次，以及 $\operatorname{sgn}(a_3 - b_3)=1$ 添加到 $c_3$。 在第四个测试用例中，看似无法提升第二个实验室的数值，但实际上可以。我们可以执行 $b_2 \mathrel{+}= \operatorname{sgn}(a_2 - c_2)$，这样就能摆脱“卡死”状态。 由 ChatGPT 5 翻译