题目描述

在平面直角坐标系中，有 $n$ 个城镇和 $m$ 个箱子。

你现在在 $(0,0)$，速度为 $1$，你需要走遍所有城镇后回到 $(0,0)$。

你可以选择走到箱子所处的位置，如果你第一次走到这个箱子，你可以吞下箱子里仅剩的一颗能量球，然后你的速度就翻倍了。

求从 $(0,0)$ 走遍所有城镇后回到 $(0,0)$ 所需的最短时间。

输入格式

第一行两个整数 $n,m$，含义如题中所述。

接下来 $n$ 行，第 $i+1$ 行两个整数表示第 $i$ 个城镇的坐标 $(x_i,y_i)$。

接下来 $m$ 行，第 $i+n+1$ 行两个整数表示第 $i$ 个箱子的坐标 $(p_i,q_i)$。

输出格式

一行一个小数，表示答案。保留 $10$ 位小数。

2 1
1 1
0 1
1 0

2.5000000000

2 1
1 1
0 1
100 0

3.4142135624

1 2
4 4
1 0
0 1

4.3713203436

提示

对于所有数据，$1\leq n\leq 12,0\leq m\leq 5,0\leq |x_i|,|y_i|,|p_i|,|q_i|\leq 10^9$。

Sample Explanation 1

路径为 $O-Chest_1-Town_1-Town_2-O$。

其中 $O$ 为原点， Chest 为加速球的编号，Town 为城镇。

Sample Explanation 2

路径为 $O-Town_1-Town_2-O$。かる