题目描述

在平面直角坐标系中，有 $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)$。

输出格式

一行一个小数，表示答案。

样例 1

输入

2 1
1 1
0 1
1 0

输出

2.5000000000

样例 2

输入

2 1
1 1
0 1
100 0

输出

3.4142135624

样例 3

输入

1 2
4 4
1 0
0 1

输出

4.3713203436

说明/提示

样例一：路径为 $O-Chest_1-Town_1-Town_2-O$。
样例二：路径为 $O-Town_1-Town_2-O$。

对于所有数据，$1\leq n\leq 12,0\leq m\leq 5,0\leq |x\_i|,|y\_i|,|p\_i|,|q\_i|\leq 10^9$。

Translate by Zek3L.