今天是 Kekoland 的回收日。为了庆祝这一节日,阿迪尔和贝拉去了中央公园公园,在那里他们可以从地上捡起瓶子,然后把它们放进回收箱。
我们可以将 Central Perk 视为坐标平面。地面上有n个瓶子,第i个瓶子位于位置(xi,yi)。阿迪尔和贝拉一次只能携带一瓶。
对于 Adil 和 Bera,流程如下所示:
1. 选择停止或继续收集瓶子。
2. 如果选择继续,则选择一些瓶子并向其走去。
3. 拿起这个瓶子,然后走到回收站。
4. 转到步骤 1。
阿迪尔和贝拉可以独立移动。允许他们同时拾取瓶子,两个人中的任何一个都可以拾取所有瓶子,允许其中一个保持静止,而另一个继续拾取瓶子。
他们希望组织这个过程,使他们行走的总距离(Adil 行走的距离和 Bera 行走的距离之和)尽可能最小。当然,最后所有瓶子都应该放入回收箱中。
输入
输入的第一行包含六个整数 ax、ay、bx、by、tx 和 ty(0 ≤ ax、ay、bx、by、tx、ty ≤ 109)——分别是 Adil、Bera 和回收箱的初始位置。
第二行包含一个整数 n (1 ≤ n ≤ 100 000) — 地面上的瓶子数量。
接下来n行,每行包含两个整数xi和yi (0 ≤ xi, yi ≤ 109)——第i个瓶子的位置。
保证Adil、Bera、回收箱和所有瓶子的位置是不同的。
输出
打印一个实数——阿迪尔和贝拉将所有瓶子放入回收箱所需步行的最小可能总距离。如果您的答案的绝对或相对误差不超过 10 - 6,则视为正确。
即:假设你的答案是a,陪审团的答案是b。如果 $$\frac{|a-b|}{\max(1,b)} \leq 10^{-6}$$,检查程序将认为您的答案正确。
示例
输入 #1
3 1 1 2 0 0 3 1 1 2 1 2 3
输出 #1
11.084259940083
输入 #2
5 0 4 2 2 0 5 5 2 3 0 5 5 3 5 3 3
输出 #2
33.121375178000
注意
考虑第一个样本。
Adil 将使用以下路径:$$(3,1)\rightarrow(2,1)\rightarrow(0,0)\rightarrow(1,1)\rightarrow(0,0)$$。
Bera 将使用以下路径:$$(1,2)\rightarrow(2,3)\rightarrow(0,0)$$。
Adil 的路径长度为 $$1 + \sqrt{5} + \sqrt{2} + \sqrt{2}$$ 单位,而 Bera 的路径长度为 $$\sqrt{2} + \sqrt{13}$$ 单位。