该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

E - 加速器

分数：500分

问题描述

在一个二维平面上，有$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$。