题目描述

外卖员 YF 获得了最佳披萨外卖员 GR 的称号。但经理不喜欢他，于是给了他一个非常困难的任务。经理给了他 $n$ 个房子的坐标 $(x_i, y_i)$，他需要将披萨送到这些房子。他将按照以下方式配送披萨：

• GR 披萨在点 $(Ax, Ay)$ 被制作，YF 从这个点开始配送。
• 他可以从 $(x, y)$ 移动到 $(x+1, y)$、$(x, y+1)$ 或 $(x, y-1)$ 这三个点中的任意一个。
• 在送完所有披萨后，他需要返回家中，即回到 $(Bx, By)$。

每次移动恰好需要一秒钟，交付披萨不用花时间（$0$ 秒）。经理希望配送用时越短越好。你需要计算完成所有 GR 披萨配送的最短时间。保证一定可以完成所有披萨的配送。

输入格式

每个测试包含若干组测试数据。第一行包含一个整数 $t$（$1 \le t \le 10^4$）——测试数据的组数。接下来是每组测试数据。

每组测试的第一行包含五个整数 $n$、$Ax$、$Ay$、$Bx$、$By$（$1 \le n \le 2 \cdot 10^5$，$1 \le Ax, Ay, Bx, By \le 10^9$），表示需要配送的房子数量及起点和终点的坐标。

第二行包含 $n$ 个整数 $x_1, x_2, \dots, x_n$（$Ax < x_i < Bx$）。

第三行包含 $n$ 个整数 $y_1, y_2, \dots, y_n$（$1 \le y_i \le 10^9$）。

保证所有组测试中 $n$ 的总和不超过 $2 \cdot 10^5$。

输出格式

对于每组测试数据，输出一个整数，占一行，表示完成披萨配送的最短时间。

样例

4
1 2 3 5 2
4
4
3 1 3 5 2
3 4 3
5 4 1
6 1 2 7 3
5 2 3 5 5 3
6 4 3 1 4 1
5 6 9 8 6
7 7 7 7 7
3 1 8 8 3

6
13
19
15

样例说明

以第二组测试数据为例：

• 从 $(Ax, Ay)$ 移动到 $(x_3, y_3)$ 需 $4$ 秒。
• 从 $(x_3, y_3)$ 移动到 $(x_1, y_1)$ 需 $4$ 秒。
• 从 $(x_1, y_1)$ 移动到 $(x_2, y_2)$ 需 $2$ 秒。
• 从 $(x_2, y_2)$ 移动到 $(Bx, By)$ 需 $3$ 秒。

总耗时 $4+4+2+3=13$ 秒。可以证明无法再更快完成配送。

由 ChatGPT 5 翻译

来源

Codeforces 2193F，英文题名 Pizza Delivery。