配点 : $500$ 点

問題文

$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}$ 以下であれば正解として扱われる。

2 1
1 1
0 1
1 0

2.5000000000

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

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

2 1
1 1
0 1
100 0

3.4142135624

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

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

1 2
4 4
1 0
0 1

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$ かかる