Sophie 是一名寻宝者。现在她正在一个由 $n$ 个洞穴组成的系统中寻找隐藏的宝藏，洞穴的编号为 $1$ 到 $n$。她知道洞穴系统中恰好有一个宝藏，且位于其中一个洞穴中。Sophie 使用探地雷达进行了一些测量；这并没有直接告诉她宝藏在哪里，但她得到了每个洞穴中含有宝藏的概率。

Sophie 将使用一个精确的远程探测器继续她的寻找：探测器进入一个洞穴后，会立即发现该洞穴是否包含宝藏。探测器在 $1$ 号洞穴开始搜索，已知该洞穴不包含宝藏。Sophie know（通过她的探地雷达测量）哪些洞穴对之间由双向通道连接，探测器可以通过这些通道。每次通过通道需要花费探测器 $1$ 分钟的时间。不幸的是，无法保证探测器能够从 $1$ 号洞穴到达其他所有洞穴（即使经过很多步）。

作为穿过通道的替代方案，Sophie 可以选择放弃当前的探测器并在系统中投入一个新的探测器，这需要花费 $t$ 分钟。如果她这样做，与旧探测器的通信将会中断，Sophie 将无法再使用它。在这些野外条件下，投入新探测器是非常不精确的：它会以 $\frac{1}{n}$ 的等概率随机降落在 $n$ 个洞穴中的任意一个。Sophie 会立即知道探测器降落在了哪里。Sophie 有无限多个探测器可供使用。

帮助 Sophie 快速找到宝藏。编写一个程序，读取洞穴系统的大小、通道的描述、引入新探测器的时间 $t$ 以及宝藏所在位置的概率分布，计算找到宝藏的最小期望时间（在 Sophie 的所有策略中取最小），并将计算出的值输出。所谓找到宝藏，是指用探测器到达含有宝藏的洞穴。

输入格式

第一行包含三个空格分隔的整数 $n, m, t$（$2 \le n \le 20$，$0 \le m \le \frac{n(n+1)}{2}$，$1 \le t \le 100$）。它们分别表示洞穴的数量、通道的数量以及投入新探测器所需的时间。

第二行包含 $n$ 个空格分隔的实数 $p_1, p_2, \dots, p_n$（$p_1 = 0$，$0 \le p_i \le 1$，$\sum_{i=1}^n p_i = 1$）；其中 $p_i$ 是宝藏在第 $i$ 个洞穴中的概率。这些值给出了两位小数的精度。

接下来的 $m$ 行描述通道。每个通道的描述包含两个空格分隔的整数 $i, j$（$1 \le i, j \le n$ 且 $i \neq j$），表示洞穴 $i$ 和 $j$ 之间有一条探测器可以双向通过的通道。你可以认为所有通道都是不同的。

输出格式

输出的第一行也是唯一一行应包含一个实数——找到宝藏的最小可能期望时间。

如果答案的绝对误差或相对误差不超过 $10^{-6}$，则认为答案是正确的。

样例

输入格式 1

4 2 10
0.00 0.00 0.50 0.50
1 2
2 3

输出格式 1

22.000000000

输入格式 2

6 5 2
0.00 0.00 0.00 0.00 0.50 0.50
1 2
2 3
3 4
4 5
5 6

输出格式 2

4.100000000

说明

在样例 1 中，Sophie 应该首先将探测器移动 to $2$ 号洞穴，然后移动到 $3$ 号洞穴。有 $\frac{1}{2}$ 的概率在时间 $2$ 时找到宝藏。如果没有找到，她现在应该开始投入新的探测器，直到有一个探测器降落在 $4$ 号洞穴。期望的投入次数为 $4$，因此在这种情况下期望的总时间为 $42$。平均而言，Sophie 需要花费 $22$ 秒来找到宝藏。（注意，在 $2$ 分钟后，Sophie 已经知道宝藏在哪里，但她仍然需要用探测器到达那里。）