102744: [AtCoder]ABC274 E - Booster

Problem Statement

In a two-dimensional plane, there are $N$ towns and $M$ chests. Town $i$ is at the coordinates $(X_i,Y_i)$, and chest $i$ is at the coordinates $(P_i,Q_i)$.

Takahashi will go on a trip where he starts at the origin, visits all $N$ towns, and then returns to the origin.
It is not mandatory to visit chests, but each chest contains an accelerator. Each time he picks up an accelerator, his moving speed gets multiplied by $2$.

Takahashi's initial moving speed is $1$. Find the shortest time needed to complete the trip.

Constraints

• $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)$, and $(P_i,Q_i)$ are distinct.
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

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

Output

Print the answer. Your output will be considered correct if the absolute or relative error from the judge's answer is at most $10^{-6}$.

Sample Input 1

2 1
1 1
0 1
1 0

Sample Output 1

2.5000000000

Here is one optimal way to complete the trip.

• Go the distance $1$ from the origin to chest $1$ at a speed of $1$, taking a time of $1$.
• Go the distance $1$ from chest $1$ to town $1$ at a speed of $2$, taking a time of $0.5$.
• Go the distance $1$ from town $1$ to town $2$ at a speed of $2$, taking a time of $0.5$.
• Go the distance $1$ from town $2$ to the origin at a speed of $2$, taking a time of $0.5$.

Sample Input 2

2 1
1 1
0 1
100 0

Sample Output 2

3.4142135624

Here is one optimal way to complete the trip.

• Go the distance $1.41\ldots$ from the origin to town $1$ at a speed of $1$, taking a time of $1.41\ldots$.
• Go the distance $1$ from town $1$ to town $2$ at a speed of $1$, taking a time of $1$.
• Go the distance $1$ from town $2$ to the origin at a speed of $1$, taking a time of $1$.

Sample Input 3

1 2
4 4
1 0
0 1

Sample Output 3

4.3713203436

Here is one optimal way to complete the trip.

• Go the distance $1$ from the origin to chest $1$ at a speed of $1$, taking a time of $1$.
• Go the distance $1.41\ldots$ from chest $1$ to chest $2$ at a speed of $2$, taking a time of $0.707\ldots$.
• Go the distance $5$ from chest $2$ to town $1$ at a speed of $4$, taking a time of $1.25$.
• Go the distance $5.65\ldots$ from town $1$ to the origin at a speed of $4$, taking a time of $1.41\ldots$.

问题描述

在一个二维平面上，有$N$个城镇和$M$个宝箱。城镇$i$在坐标$(X_i,Y_i)$，宝箱$i$在坐标$(P_i,Q_i)$。

高桥将进行一次旅行，从原点出发，访问所有$N$个城镇，然后返回原点。
访问宝箱不是强制性的，但每个宝箱都包含一个加速器。每次他拾取一个加速器，他的移动速度就会乘以$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$。
• 以速度$2$从宝箱$1$到城镇$1$的距离$1$，花费时间为$0.5$。
• 以速度$2$从城镇$1$到城镇$2$的距离$1$，花费时间为$0.5$。
• 以速度$2$从城镇$2$到原点的距离$1$，花费时间为$0.5$。

样例输入2

2 1
1 1
0 1
100 0

样例输出2

3.4142135624

以下是完成旅行的一种最优方式。

• 以速度$1$从原点到城镇$1$的距离$1.41\ldots$，花费时间为$1.41\ldots$。
• 以速度$1$从城镇$1$到城镇$2$的距离$1$，花费时间为$1$。
• 以速度$1$从城镇$2$到原点的距离$1$，花费时间为$1$。

样例输入3

1 2
4 4
1 0
0 1

样例输出3

4.3713203436

以下是完成旅行的一种最优方式。

• 以速度$1$从原点到宝箱$1$的距离$1$，花费时间为$1$。
• 以速度$2$从宝箱$1$到宝箱$2$的距离$1.41\ldots$，花费时间为$0.707\ldots$。
• 以速度$4$从宝箱$2$到城镇$1$的距离$5$，花费时间为$1.25$。
• 以速度$4$从城镇$1$到原点的距离$5.65\ldots$，花费时间为$1.41\ldots$。