E. Points Selectiontime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard outputAlice 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: First, Alice selects some points (possibly none, but not all) and removes them from the field. 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$$$.InputThe 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$$$. OutputFor each test case, output a single integer — the final score of the game if both Alice and Bob play optimally.ExampleInput414242100045 10 5 00 5 10 51 1 1 146 7 8 93 3 3 39 0 9 021000000000 1010 100000000012345 54321Output040223999999960NoteIn 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$$$.