CF2169E.Points Selection

Alice and Bob are playing with points on the XY plane. Initially, there are $n$ points on the plane: the $i$-th point is located at $(x_i, y_i)$ and has a cost of $c_i$.

The game consists of two stages:

1. First, Alice selects some points (possibly none, but not all) and removes them from the field.
2. Then, Bob draws a rectangle with sides parallel to the coordinate axes, such that all remaining points lie inside or on the boundary of this rectangle. The rectangle can degenerate into a line segment or even a point.

After that, the game ends and the total score is calculated. The total score of the game is the sum of the costs of the removed points by Alice and the perimeter of the rectangle drawn by Bob. Alice wants to maximize the score, while Bob wants to minimize it.

Determine the total score of the game if both Alice and Bob play optimally.

The perimeter of the rectangle is equal to the sum of the lengths of all its four sides. Therefore, even if the rectangle degenerates into a line segment of length $k$, its perimeter will be $2k$. The perimeter of a rectangle that degenerates into a point is $0$.

爱丽丝和鲍勃正在 XY 平面上玩点的游戏。初始时，平面上有 $n$ 个点：第 $i$ 个点位于 $(x_i, y_i)$，其代价为 $c_i$。

游戏分为两个阶段：

1. 首先，爱丽丝选择若干个点（可以一个都不选，但不能全部选）并将其从平面上移除；
2. 接着，鲍勃画一个边与坐标轴平行的矩形，使得所有剩余的点均位于该矩形内部或边界上。该矩形可以退化为一条线段，甚至一个点。

此后游戏结束，并计算总得分。游戏总得分为：爱丽丝移除的点的代价之和，加上鲍勃所画矩形的周长。爱丽丝希望最大化总得分，而鲍勃希望最小化总得分。

若双方均采取最优策略，请确定游戏的总得分。

矩形的周长等于其四条边长度之和。因此，即使矩形退化为一条长度为 $k$ 的线段，其周长也为 $2k$；而退化为一个点的矩形，其周长为 $0$。

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($1 \le n \le 3 \cdot 10^5$) — the number of points on the plane.

The second line of each test case contains $n$ integers $x_1, x_2, \dots, x_n$ ($0 \le x_i \le 10^{15}$) — the $x$-coordinates of the points.

The third line contains $n$ integers $y_1, y_2, \dots, y_n$ ($0 \le y_i \le 10^{15}$) — the $y$-coordinates of the points.

The fourth line contains $n$ integers $c_1, c_2, \dots, c_n$ ($0 \le c_i \le 10^9$) — the costs of the points.

Additional constraints on the input:

• in one test case, all points are pairwise distinct;
• the total number of points across all test cases does not exceed $3 \cdot 10^5$.

第一行包含一个整数 $t$（$1 \le t \le 10^4$）——测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 3 \cdot 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 \cdot 10^5$。

For each test case, output a single integer — the final score of the game if both Alice and Bob play optimally.

对于每个测试用例，输出一个整数——即当爱丽丝和鲍勃均采取最优策略时，游戏的最终得分。

In the first test case, there is only one point, and Alice cannot remove it. Then Bob constructs the rectangle $(1, 1) - (1, 1)$ with a perimeter of $0$.

In the second test case, it is optimal for Alice not to remove any points. Then Bob constructs the rectangle $(0, 0) - (10, 10)$ with a perimeter of $40$.

In the third test case, it is optimal for Alice to remove the first and third points. Then Bob constructs the rectangle $(7, 3) - (9, 3)$ with a perimeter of $4$. The total score will be $9 + 9 + 4 = 22$.

在第一个测试用例中，只有一个点，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$。