← 返回题目列表

Codeforces · 2169/E

E. 点选择

中文机器翻译题面 查看原题

Alice 和 Bob 正在玩 XY 平面上的点。最初,平面上有 $$$n$$$ 个点:第 $$$i$$$ 个点位于 $$$(x_i, y_i)$$$,成本为 $$$c_i$$$。

游戏分为两个阶段:

  1. 首先,Alice 选择一些点(可能没有,但不是全部)并 删除 他们来自外地。
  2. 然后,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 都表现最佳,则为游戏的最终得分。

示例

输入
复制

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

输出
复制

0
40
22
3999999960

注意

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