[FJOI2018]邮递员问题

题目描述

$\text{2010}$ 年以来,网购市场发展迅速,快递公司成为促成交易成功的关键环节。小郭是一名顺丰快递员,他的工资主要包括底薪、送货提成、收件提成、其他福利补贴等。小郭每完成一件客户的快递单,一般能拿到运费 $10\%$ 的提成。因此小郭完成的快递单越多越快,他的收入就越高。小郭负责城市中 $2$ 个平行街道的所有快递业务。在这 $2$ 个平行街道上有 $2$ 处快递工作站。小郭每次投递的行程都是从一个工作站出发,完成所有快递单的投递后,回到另一个工作站。为了高效地完成投递任务,小郭希望用最短的行程来完成所有快递单的投递任务。也就是说,对于给定的 $2$ 个平行街道的街距和 $2$ 个工作站位置,以及所有投递点的位置,小郭要计算从一个工作站出发,完成所有快递单的投递后,回到另一个工作站的最短行程。街距是指 $2$ 个平行街道的之间的垂直距离。如果设平面坐标系的 $x$ 轴与街道平行,且 $2$ 个平行街道上的最左端位置的 $x$ 坐标均为 $0$,则 $2$ 个平行街道上的任何位置可以用从街道最左端到该位置的直线距离,即该位置的 $x$ 坐标值来表示。 例如,设 $2$ 个平行街道 A 和 B 的街距是 $2$。$2$ 个工作站 $S_1$ ​​和 $S_2$​​ 的位置分别位于街道 A 的 $x=1$ 和街道 B 的 $x=3$ 处。另外有 $2$ 个投递点 $T_1$ 和 $T_2$​ 的位置分别位于街道 A 的 $x=3$ 和街道 B 的 $x=1$ 处,如图所示。小郭的任务就是要从工作站 $S_1$​​ 出发,完成在 $T_1$​​ 和 $T_2$​​ 处的快递单投递后,回到另一个工作站 $S_2$。 编程任务:对于给定的 $2$ 个平行街道的街距和 $2$ 个工作站位置,以及所有投递点的位置,计算从一个工作站出发,完成所有快递单的投递后,回到另一个工作站的最短行程。

输入输出格式

输入格式


第 $1$ 行有 $2$ 个正整数 $n,m$,$1 \le n,m \le 10000$,分别表示 $2$ 个平行街道 A 和 B 上的位置数(包括投递点的位置和工作站的位置)。位置编号为 A:$1,2,\ldots,n$;B:$1,2,\ldots,m$。 第 $2$ 行有 $4$ 个正整数 $a,b,c,d$,表示 $2$ 个工作站位置分别为 $(a,b)$ 和 $(c,d)$。$a=0$ 或 $c=0$ 表示相应的工作站在街道 $A$,$a=1$ 或 $c=1$ 表示相应的工作站在街道 $B$。$b$ 和 $d$ 分别表示工作站在相应的街道的位置号。例如,若 $(a,b)=(0,3)$ 表示第 $1$ 个工作站位于街道 $A$ 上,其位置位于给出的街道 $A$ 的 $n$ 个位置的第 $3$ 个位置。 第 $3$ 行有 $1$ 个实数 $h$,表示 $2$ 个平行街道的街距 $(1 \le h \le 10)$。 第 $4$ 行有 $n$ 个实数,表示街道 $A$ 上 $n$ 个位置的 $x$ 坐标 $(1 \le x < 20000)$。 第 $5$ 行有 $m$ 个实数,表示街道 $B$ 上 $m$ 个位置的 $x$ 坐标 $(1 \le x < 20000)$。

输出格式


输出计算出的最短行程,保留 $2$ 位小数。

输入输出样例

输入样例 #1

2 2
0 1 1 2
2
1 3
1 3

输出样例 #1

6.83

说明

对于 $10\%$ 的数据,$n,m\le 8$; 对于 $30\%$ 的数据,$n,m\le 100$; 对于 $50\%$ 的数据,$n,m\le 1000$; 对于 $100\%$ 的数据,$n,m\le 10000$。