Caves

Sophie is a treasure seeker. She is looking for a treasure hidden in a system of $n$ caves, numbered from $1$ to $n$. The cave system contains exactly one treasure, in one of the caves. Sophie used a georadar, which did not reveal where the treasure is, but gave her a probability for each cave that the treasure is in that cave.

Sophie continues the search with a precise remote probe. When the probe enters a cave, it immediately finds out whether that cave contains the treasure. The probe starts in cave $1$, and it is known that this cave does not contain the treasure. Sophie knows which pairs of caves are connected by bidirectional tunnels that the probe can traverse. Each traversal takes the probe one minute. The probe may not be able to reach every cave, even in many steps.

Instead of traversing a tunnel, Sophie can abandon the probe and insert a new one, which takes $t$ minutes. The old probe is then lost, and Sophie can no longer use it. A new probe is imprecise: it lands in each of the $n$ caves with probability $\frac{1}{n}$. Sophie immediately learns where the probe has landed. Sophie has infinitely many probes.

Help Sophie find the treasure quickly. Given the size of the cave system, the tunnels, the insertion time $t$, and the probability distribution of the treasure, compute the smallest expected time over all of Sophie's strategies. Finding the treasure means reaching the treasure cave with a probe.

The first line contains three space-separated integers $n$, $m$, $t$ ($2 \le n \le 20$, $0 \le m \le \frac{n(n+1)}{2}$, $1 \le t \le 100$). They denote the number of caves, the number of tunnels, and the time needed to insert a new probe.

The second line contains $n$ space-separated real numbers $p_1, p_2, \ldots, p_n$ ($p_1 = 0$, $0 \le p_i \le 1$, $\sum_{i=1}^{n} p_i = 1$). The number $p_i$ is the probability that the treasure is in cave $i$. These values have two decimal digits of precision.

Each of the next $m$ lines contains two space-separated integers $i$, $j$ ($1 \le i, j \le n$, $i \ne j$), describing a tunnel between caves $i$ and $j$ that the probe can traverse in either direction. All tunnels are distinct.

Print one real number, the minimum possible expected time of finding the treasure. The answer is accepted if its absolute or relative error is at most $10^{-6}$.

In sample 1, Sophie first moves the probe to cave $2$, then to cave $3$. With probability $\frac{1}{2}$, she finds the treasure at time $2$. Otherwise, she inserts new probes until one lands in cave $4$. The expected number of insertions is $4$, so the expected total time in this case is $42$. On average, Sophie finds the treasure in $22$ seconds. After $2$ minutes, Sophie already knows where the treasure is, but she still needs a probe to reach it.