CF2169E Points Selection

Alice 和 Bob 在 $XY$ 平面上玩点的游戏。最开始，平面上有 $n$ 个点：第 $i$ 个点的坐标为 $(x_i, y_i)$，并且有一个代价 $c_i$。 游戏分为两个阶段： 1. 首先，Alice 可以选择若干个点（可以一个都不选，但不能全选）并将这些点移除。 2. 然后，Bob 画一个边平行于坐标轴的矩形，使得所有剩下的点都在该矩形内或在其边界上。该矩形可以退化为线段甚至一个点。 之后，游戏结束并计算总分。总分为 Alice 移除的点的代价之和，加上 Bob 所画矩形的周长。Alice 想要最大化总分，而 Bob 想最小化总分。 请你在两人都采取最优策略的情况下，计算该游戏的最终分数。 矩形的周长定义为其四条边长度之和。因此，即使矩形退化为长度为 $k$ 的线段，其周长为 $2k$。如果矩形退化为一个点，则周长为 $0$。

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 3 \times 10^5$），表示平面上的点数。 每个测试用例的第二行包含 $n$ 个整数 $x_1, x_2, \dots, x_n$（$0 \le x_i \le 10^{15}$），表示各个点的 $x$ 坐标。 第三行包含 $n$ 个整数 $y_1, y_2, \dots, y_n$（$0 \le y_i \le 10^{15}$），表示各个点的 $y$ 坐标。 第四行包含 $n$ 个整数 $c_1, c_2, \dots, c_n$（$0 \le c_i \le 10^9$），表示各个点的代价。 附加约束： - 每个测试用例中，所有点两两不同。 - 所有测试用例中点的总数不超过 $3 \times 10^5$。

对于每个测试用例，输出一个整数，表示在 Alice 和 Bob 都采取最优策略情况下的最终得分。

在第一个测试用例中，只有一个点，Alice 不能将其移除。此时 Bob 画出的矩形为 $(1, 1)-(1, 1)$，周长为 $0$。 在第二个测试用例中，Alice 最优选择是不移除任何点。此时 Bob 画出的矩形为 $(0, 0)-(10, 10)$，周长为 $40$。 在第三个测试用例中，Alice 最优选择是移除第一个和第三个点。此时 Bob 画出的矩形为 $(7, 3)-(9, 3)$，周长为 $4$。总得分为 $9+9+4=22$。 由 ChatGPT 5 翻译