Alice 和 Bob 正在玩 XY 平面上的点。最初,平面上有 $$$n$$$ 个点:第 $$$i$$$ 个点位于 $$$(x_i, y_i)$$$,成本为 $$$c_i$$$。
游戏分为两个阶段:
- 首先,Alice 选择一些点(可能没有,但不是全部)并 删除 他们来自外地。
- 然后,Bob 绘制一个边与坐标轴平行的矩形,使得所有剩余的点都位于该矩形的内部或边界上。矩形可以退化为线段甚至点。
之后,游戏结束,计算总分。游戏的总得分是各回合花费的总和 已删除 点由爱丽丝和 周长 Bob 绘制的矩形的 。 Alice 想要最大化分数,而 Bob 想要最小化分数。
如果 Alice 和 Bob 都发挥最佳,则确定游戏的总得分。 矩形的
的 周长 Bob 绘制的矩形的 等于其所有边的长度之和 四 双方。因此,即使矩形退化为长度为 $$$k$$$ 的线段,其周长也将为 $$$2k$$$。退化为点的矩形的周长是$$$0$$$。
输入
第一行包含一个整数 $$$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$$$。
输出
对于每个测试用例,输出一个整数 - 如果 Alice 和 Bob 都表现最佳,则为游戏的最终得分。
示例
输入复制
414242100045 10 5 00 5 10 51 1 1 146 7 8 93 3 3 39 0 9 021000000000 1010 100000000012345 54321
输出复制
040223999999960
注意
在第一个测试用例中,只有一个点,Alice 无法删除它。然后 Bob 构造周长为 $$$0$$$ 的矩形 $$$(1, 1) - (1, 1)$$$。
在第二个测试用例中,Alice 最好不要删除任何点。然后 Bob 构造了周长为 $$$40$$$ 的矩形 $$$(0, 0) - (10, 10)$$$。
在第三个测试用例中,Alice 删除第一点和第三点是最佳的。然后 Bob 构造周长为 $$$4$$$ 的矩形 $$$(7, 3) - (9, 3)$$$。总分将为 $$$9 + 9 + 4 = 22$$$。