You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

连线问题

Description

在二维平面上，直线 $y=A$上有 $N$个点，坐标为 $(a[1...n],A)$ 直线$y=b$上有m个点，坐标为$(b[1...m],B)$； 任意两点之间连线的代价为它们的欧几里得距离 $dis=sqrt((x_{1}-x_{2})^{2}+y_{1}-y_{2})^{2})$ 现在你想把这 {n+m}l联通（任意两点间有路径），求最小总代价

Format

输入格式

第一行四个整数$n,m,a,b$ 第二行$n$个整数$da[1...n]$,为$a$的差分数组（即距离上一个点的距离） 第二行$m$个整数$db[1...n]$,为$b$的差分数组

输出格式

输出一个小数，代表最小总代价，保留小数点后2位

样例

2 3 1 3
1 2
2 2 

7.24

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

2001141.99

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

29.28

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

35.99

数据范围

对于 10% 的数据，$n,m \leq 10$ 对于 40% 的数据，$n,m \leq 10^{3}$ 对于 70% 的数据，$n,m \leq 10^{5}$ 对于 100% 的数据，$n,m \leq 6*10^{5}$,$1 \leq a[i],b[i] \leq 10^{8}$, $1 \leq A,B \leq 2000$