AT_abc274_e [ABC274E] Booster

[problemUrl]: https://atcoder.jp/contests/abc274/tasks/abc274_e $ 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} $ 以下であれば正解として扱われる。

### 制約 - $ 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 $ かかる