连线问题

题目描述

二维平面上：

• 直线 $y=A$ 上有 $n$ 个点 $(a[1...n],A)$
• 直线 $y=B$ 上有 $m$ 个点 $(b[1...m],B)$
  两点连线代价为欧几里得距离。求 n+m 个点联通的最小总代价。

输入格式

• 第一行 4 个整数 $n,m,A,B$
• 第二行 n 个整数 $da[1...n]$（$a$ 数组的差分）
• 第三行 m 个整数 $db[1...m]$（$b$ 数组的差分）

输出格式

• 最小总代价（保留 2 位小数）

样例

样例 1 输入

2 3 1 3
1 2
2 2 1

样例 1 输出

7.24

样例 2 输入

10 10 10 1000
1 2000000 10 10 10 10 10 10 10 1
1000006 1000000 10 10 10 10 10 10 10 10

样例 2 输出

2001141.99

数据范围

• 10% 数据：$n,m ≤ 10$
• 40% 数据：$n,m ≤ 10^3$
• 70% 数据：$n,m ≤ 10^5$
• 100% 数据：$n,m ≤ 6×10^5$, $1≤a[i]$,$b[i]≤10^5$, $1≤A,B<2000$