问题描述

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

Takahashi 将进行一次旅行，他从原点出发，访问所有 $N$ 个城镇，然后返回原点。
访问宝箱并非强制性的，但每个宝箱都含有加速器。每次拾起一个加速器，他的移动速度就会乘以 $2$。

Takahashi 的初始移动速度为 $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$。