连线问题

题目描述

在二维平面上，直线 $x=0$ 上有 $n$ 个点，坐标为 $(0, y_i)$； 直线 $x=d$ 上有 $m$ 个点，坐标为 $(d, z_j)$。

任意两点之间连线的代价为它们的欧几里得距离。 现在你想把这 $n + m$ 个点联通（任意两点之间有路径），求问最小总代价。

输入格式

• 第一行四个整数 $n, m, d, p$
  • $p$ 是差分数组的长度（见下）
• 第二行 $p$ 个整数 $dy_1, dy_2, ..., dy_p$，为 $y$ 数组的差分数组（即距离上一个点的距离）
• 第三行 $p$ 个整数 $dz_1, dz_2, ..., dz_p$，为 $z$ 数组的差分数组

注：实际的 $y$ 和 $z$ 数组通过累加差分数组生成，长度为 $n$ 和 $m$

输出格式

• 输出一个小数，代表最小总代价，保留小数点后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

样例输入3

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

样例输出3

29.28

样例输入4

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

样例输出4

35.99

数据范围

• 对于 10% 的数据，$n, m \leq 10$
• 对于 40% 的数据，$n, m \leq 100$
• 对于 70% 的数据，$n, m \leq 1000$
• 对于 100% 的数据，$n, m \leq 10^6, d \leq 10^9$