E. Points Selection
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

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$$$.

Input

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$$$.
Output

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

Example
Input
4
1
42
42
1000
4
5 10 5 0
0 5 10 5
1 1 1 1
4
6 7 8 9
3 3 3 3
9 0 9 0
2
1000000000 10
10 1000000000
12345 54321
Output
0
40
22
3999999960
Note

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$$$.