問題文

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

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

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

制約

• $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)$ は相異なる
• 入力は全て整数

入力

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

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

出力

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

入力例 1

2 1
1 1
0 1
1 0

出力例 1

2.5000000000

以下のように移動するのが最適解の一つです。

• 原点から宝箱 $1$ までの距離 $1$ を速さ $1$ で移動する。時間が $1$ かかる
• 宝箱 $1$ から街 $1$ までの距離 $1$ を速さ $2$ で移動する。時間が $0.5$ かかる
• 街 $1$ から街 $2$までの距離 $1$ を速さ $2$ で移動する。時間が $0.5$ かかる
• 街 $2$から原点までの距離 $1$ を速さ $2$ で移動する。時間が $0.5$ かかる

入力例 2

2 1
1 1
0 1
100 0

出力例 2

3.4142135624

以下のように移動するのが最適解の一つです。

• 原点 から街 $1$ までの距離 $1.41\\ldots$ を速さ $1$ で移動する。時間が $1.41\\ldots$ かかる
• 街 $1$ から街 $2$ までの距離 $1$ を速さ $1$ で移動する。時間が $1$ かかる
• 街 $2$ から原点までの距離 $1$ を速さ $1$ で移動する。時間が $1$ かかる

入力例 3

1 2
4 4
1 0
0 1

出力例 3

4.3713203436

以下のように移動するのが最適解の一つです。

• 原点から宝箱 $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$ かかる