Explorer

题目描述

给出两条直线,上面分别有n,m个点,求其最小生成树。

输入输出格式

输入格式


输入包括5行。 第一行为n和m。 第二行为四个整数AX AY BX BY。 第三行为四个整数CX CY DX DY。 第四行为n个实数,代表在第一条直线上的n个点。对于某个点,用一个实数t来表示该点的坐标为(AX \* t + BX \* (1 - t), AY \* t + BY \* (1 - t))。 第五行为m个实数,代表第二条直线上的m个点,表示方法同上。

输出格式


一行一个实数,为其最小生成树长度,四舍五入至三位小数。

输入输出样例

输入样例 #1

4 4 
0 0 10 10 
0 10 10 0 
0.1 0.3 0.6 0.8 
0.1 0.3 0.6 0.8

输出样例 #1

19.638

说明

30%的数据:n,m <= 1000 100%的数据:n,m <= 100000 AX,AY,BX,BY,CX,CY,DX,DY的绝对值均小于等于100000 0 <= t <= 1