加速器

题目描述

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

高桥君将进行一段旅行:从原点出发,访问全部 $N$ 个城镇,然后回到原点。

宝箱不强制访问,但每个宝箱里都装有加速器。每拾起一个加速器,他的移动速度就会乘以 $2$。

高桥君的初始移动速度为 $1$。求完成旅行所需的最短时间。

输入格式

输入按以下格式从标准输入给出:

$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$ 以速度 $2$ 移动距离 $1$ 到达城镇 $1$,耗时 $0.5$。

从城镇 $1$ 以速度 $2$ 移动距离 $1$ 到达城镇 $2$,耗时 $0.5$。

从城镇 $2$ 以速度 $2$ 移动距离 $1$ 到达原点,耗时 $0.5$。

2 1
1 1
0 1
100 0

3.4142135624

下面是一种最优的完成旅行的方法。

从原点以速度 $1$ 移动距离 $1.41\ldots$ 到达城镇 $1$,耗时 $1.41\ldots$。

从城镇 $1$ 以速度 $1$ 移动距离 $1$ 到达城镇 $2$,耗时 $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$ 以速度 $4$ 移动距离 $5$ 到达城镇 $1$,耗时 $1.25$。

从城镇 $1$ 以速度 $4$ 移动距离 $5.65\ldots$ 到达原点,耗时 $1.41\ldots$。

数据范围

• $1 \le N \le 12$
• $0 \le M \le 5$
• $-10^9 \le X_i,Y_i,P_i,Q_i \le 10^9$
• $(0,0)$、$(X_i,Y_i)$ 和 $(P_i,Q_i)$ 两两不同
• 输入中的所有值均为整数