← 返回题目列表

Codeforces · 2193/F

F. 披萨外卖

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

快递员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 \lt x_i \lt 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

注意

考虑第二个测试用例:

  • 在 $$$4$$$ 秒内从点 ($$$Ax, Ay$$$) 移动到点 ($$$x_3, y_3$$$)。
  • 在 $$$4$$$ 秒内从点 ($$$x_3, y_3$$$) 移动到点 ($$$x_1, y_1$$$)。
  • 在 $$$2$$$ 秒内从点 ($$$x_1, y_1$$$) 移动到点 ($$$x_2, y_2$$$)。
  • 在 $$$3$$$ 秒内从点 ($$$x_2, y_2$$$) 移动到点 ($$$Bx, By$$$)。
递送总共需要 $$$4 + 4 + 2 + 3 = 13$$$ 秒。事实证明,不可能更快地送出披萨。