A115474.单向配送

普及+/提高

官方

通过率:0%

时间限制:1.00s

内存限制:512MB

题目描述

平面上有 nn 个投递点,第 ii 个投递点坐标为 (xi,yi)(x_i,y_i)

骑手从起点 (Ax,Ay)(A_x,A_y) 出发,最后需要到达终点 (Bx,By)(B_x,B_y)。在整个过程中,他只能执行下面三种移动:

  • (x,y)(x+1,y)(x,y)\to(x+1,y)
  • (x,y)(x,y+1)(x,y)\to(x,y+1)
  • (x,y)(x,y1)(x,y)\to(x,y-1)

每移动一次耗时 11,在投递点停下交付不额外耗时。

要求他在途中访问所有投递点至少一次,然后到达终点。已知一定存在可行路线。

请你求出最短总时间。

输入格式

第一行一个整数 tt,表示测试组数。

对于每组数据:

  • 第一行五个整数 n,Ax,Ay,Bx,Byn,A_x,A_y,B_x,B_y
  • 第二行 nn 个整数 x1,x2,,xnx_1,x_2,\dots,x_n
  • 第三行 nn 个整数 y1,y2,,yny_1,y_2,\dots,y_n

输出格式

对每组数据输出一个整数,表示最短时间。

输入输出样例

  • 输入#1

    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
    

    输出#1

    6
    13
    19
    15
    

说明/提示

数据范围

  • 1t1041 \le t \le 10^4
  • 1n2×1051 \le n \le 2\times 10^5
  • 1Ax,Ay,Bx,By1091 \le A_x,A_y,B_x,B_y \le 10^9
  • Ax<xi<BxA_x < x_i < B_x
  • 1yi1091 \le y_i \le 10^9
  • 所有测试组的 nn 之和不超过 2×1052\times 10^5
首页