题目描述

$2$ 次元平面上に $N$ 個の街と $M$ 個の宝箱があります。街 $i$ は座標 $(X_i,Y_i)$ に、宝箱 $i$ は座標 $(P_i,Q_i)$ にあります。

高橋君は原点を出発し、$N$ 個の街全てを訪れたのち原点に戻る旅行をしようと考えています。
宝箱を訪れる必要はありませんが、宝箱の中にはそれぞれブースターが $1$ つあり、ブースターを拾うごとに移動速度が $2$ 倍になります。

高橋君の最初の移動速度が単位時間あたり $1$ であるとき、旅行にかかる時間の最小値を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $X_1$ $Y_1$ $\vdots$ $X_N$ $Y_N$ $P_1$ $Q_1$ $\vdots$ $P_M$ $Q_M$

输出格式

答えを出力せよ。なお、想定解答との絶対誤差または相対誤差が $10^{-6}$ 以下であれば正解として扱われる。

题目大意

题目描述

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

输出格式

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

数据范围与提示

样例一：路径为 $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.

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$
• $-10^9\ \leq\ X_i,Y_i,P_i,Q_i\ \leq\ 10^9$
• $(0,0),(X_i,Y_i),(P_i,Q_i)$ は相異なる
• 入力は全て整数

Sample Explanation 1

以下のように移動するのが最適解の一つです。 - 原点から宝箱 $1$ までの距離 $1$ を速さ $1$ で移動する。時間が $1$ かかる - 宝箱 $1$ から街 $1$ までの距離 $1$ を速さ $2$ で移動する。時間が $0.5$ かかる - 街 $1$ から街 $2$までの距離 $1$ を速さ $2$ で移動する。時間が $0.5$ かかる - 街 $2$から原点までの距離 $1$ を速さ $2$ で移動する。時間が $0.5$ かかる

Sample Explanation 2

以下のように移動するのが最適解の一つです。 - 原点 から街 $1$ までの距離 $1.41\ldots$ を速さ $1$ で移動する。時間が $1.41\ldots$ かかる - 街 $1$ から街 $2$ までの距離 $1$ を速さ $1$ で移動する。時間が $1$ かかる - 街 $2$ から原点までの距離 $1$ を速さ $1$ で移動する。時間が $1$ かかる

Sample Explanation 3

以下のように移動するのが最適解の一つです。 - 原点から宝箱 $1$ までの距離 $1$ を速さ $1$ で移動する。時間が $1$ かかる - 宝箱 $1$ から宝箱 $2$ までの距離 $1.41\ldots$ を速さ $2$ で移動する。時間が $0.707\ldots$ かかる - 宝箱 $2$ から街 $1$ までの距離 $5$ を速さ $4$ で移動する。時間が $1.25$ かかる - 街 $1$ から原点までの距離 $5.65\ldots$ を速さ $4$ で移動する。時間が $1.41\ldots$ かかる