题目背景

Caesar 远征高卢回来后，对你大加赞赏，他亲自来到 Genoa 视察。

Genoa 在你的建设下变得无比繁荣，由于财政收入的增加，你为城市修建了交通系统。古罗马的交通系统由两部分组成——Dirt Road 和 Rome Road。两个路口间只可能是其中一种道路。在 Rome Road 上可以驾驶马车，而在 Dirt Road 上则不行。由于修建道路是一项浩大的工程，使得你无法将整个城市用 Rome Road 连接起来。

现在 Caesar 已经到达码头，他要求去你家参观。Caesar 有一个癖好，喜欢坐车而不喜欢走路。所以 Caesar 走 Dirt Road 时的不满值要比走 Rome Road 时大。

为了不让 Caesar 过于不满而罢免你的职位，请设计路线使得 Caesar 的不满值最小。

题目描述

给定一张二维平面上 $n+2$ 个结点的无向完全图（也就是说，每两个点之间都有一条边），其中 $i$ 号点的坐标为 $A_i(x_i,y_i)$。

无向图中有两种边，一种叫 Rome Road，一种叫 Dirt Road。

记所有 Rome Road 的集合为 $S$，$l(X,Y)$ 表是线段 $XY$ 的长度，则一条边 $(A_i,A_j)$ 的边权为：

$$c(A_i,A_j)=\begin{cases}d_R \cdot l(A_i,A_j),&(A_i,A_j) \in S\\d_D \cdot l(A_i,A_j),&(A_i,A_j) \notin S\end{cases} $$

即该边的长度与对应系数（Rome Road 为 $d_R$，Dirt Road 为 $d_D$）的乘积。

保证所有与 $n+1$ 号结点和 $n+2$ 号结点相连的所有边都是 Dirt Road。

现在，你需要求出 $n+1$ 号结点和 $n+2$ 号结点之间的最短路。

输入格式

第一行两个小数 $d_D,d_R$。

第二行一个正整数 $n$。

下面 $n$ 行，第 $i$ 行两个小数 $x_i,y_i$。

下面若干行（以 0 0 为结束标志），每行两个正整数 $u,v$，表示边 $(u,v)$ 是 Rome Road。

下面一行两个小数 $x_{n+1},y_{n+1}$。

最后一行两个小数 $x_{n+2},y_{n+2}$。

输出格式

求出 $n+1$ 号结点和 $n+2$ 号结点之间的最短路，答案保留 $4$ 位小数。

100.0 2.0
2
1.0 0.0
2.0 1.0
1 2
0 0
0.0 0.0
2.0 2.0

202.8284

提示

对于 $100\%$ 的数据：

• $0.1 \le d_R < d_D \le 10^3$
• $0 \le p(d_D),p(d_R) \le 1$
• $1 \le n \le 10^3$
• $0 \le x_i,y_i \le 10^4$
• $0 \le p(x_i),p(y_i) \le 2$
• Rome Road 不超过 $200$ 条
• $1 \le u,v \le n$（结束标志除外）
• $u \ne v$

其中 $p(X)$ 表示小数 $X$ 的小数位数。