说明

给出两条直线，上面分别有 $n,m$ 个点，求这 $n+m$ 个点组成的最小生成树。

输入格式

输入包括 $5$ 行。

第一行为 $n$ 和 $m$。

第二行为四个整数 $x_a,y_a,x_b,y_b$。

第三行为四个整数 $x_c,y_c,x_d,y_d$。

第四行为 $n$ 个实数，代表在第一条直线上的 $n$ 个点。对于某个点，用一个实数 $t$ 来表示该点的坐标为 $(t x_a + (1 - t)x_b, t y_a + (1 - t) y_b)$。

第五行为 $m$ 个实数，代表第二条直线上的 $m$ 个点，表示方法同上。

输出格式

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

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

19.638

提示

$1 \le n,m \le 100000$，$x_a,y_a,x_b,y_b,x_c,y_c,x_d,y_d$ 的绝对值均小于等于 $10^5$，$0 \le t \le 1$。

2024/2/8 添加一组 hack 数据。