동굴

소피는 보물 사냥꾼이다. 그녀는 1번부터 $n$번까지 번호가 매겨진 $n$개의 동굴로 이루어진 동굴 체계에서 보물을 찾고 있다. 보물은 정확히 한 동굴에 있다. 소피는 지표 레이더로 측정을 해 보았지만 보물의 위치는 알아내지 못했고, 각 동굴에 보물이 있을 확률만 얻었다.

소피는 정밀한 원격 탐침으로 탐색을 계속한다. 탐침이 동굴에 들어가면 그 동굴에 보물이 있는지 즉시 알 수 있다. 탐침은 1번 동굴에서 출발하며, 1번 동굴에는 보물이 없다는 것이 알려져 있다. 소피는 탐침이 지날 수 있는 양방향 터널로 연결된 동굴 쌍을 알고 있다. 터널을 한 번 지날 때마다 1분이 걸린다. 탐침이 여러 단계를 거쳐도 모든 동굴에 갈 수 있다는 보장은 없다.

터널을 지나는 대신, 소피는 탐침을 버리고 새 탐침을 넣을 수 있으며, 이때 $t$분이 걸린다. 그러면 옛 탐침과의 통신은 끊기고 소피는 더 이상 그 탐침을 쓸 수 없다. 새 탐침은 정밀하지 않아서 $n$개 동굴 각각에 $\frac{1}{n}$의 확률로 떨어진다. 소피는 새 탐침이 어디에 떨어졌는지 즉시 안다. 소피에게 쓸 수 있는 탐침은 무한히 많다.

보물을 빨리 찾도록 도와 달라. 동굴 체계의 크기, 터널, 탐침 삽입 시간 $t$, 보물의 확률분포가 주어졌을 때, 소피의 모든 전략 가운데 보물을 찾는 기대 시간의 최솟값을 구하라. 보물을 찾는다는 것은 탐침으로 보물이 있는 동굴에 도달하는 것을 뜻한다.

첫 줄에 공백으로 구분된 세 정수 $n$, $m$, $t$ ($2 \le n \le 20$, $0 \le m \le \frac{n(n+1)}{2}$, $1 \le t \le 100$)가 주어진다. 각각 동굴 수, 터널 수, 새 탐침을 삽입하는 데 걸리는 시간이다.

둘째 줄에는 공백으로 구분된 실수 $p_1, p_2, \ldots, 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 \ne j$)가 주어진다. 이는 $i$번 동굴과 $j$번 동굴 사이의 터널을 뜻하며, 탐침은 어느 방향으로든 이 터널을 지날 수 있다. 모든 터널은 서로 다르다.

보물을 찾는 기대 시간의 최솟값을 나타내는 실수 하나를 출력한다. 절대 오차 또는 상대 오차가 $10^{-6}$ 이하이면 정답으로 인정한다.

샘플 1에서 소피는 먼저 탐침을 2번 동굴로, 그다음 3번 동굴로 옮겨야 한다. 확률 $\frac{1}{2}$로 시간 2에 보물을 찾는다. 찾지 못했다면 새 탐침이 4번 동굴에 떨어질 때까지 탐침을 계속 삽입한다. 삽입 횟수의 기대값은 $4$이므로, 이 경우 총 기대 시간은 $42$다. 평균적으로 소피는 $22$초 만에 보물을 찾는다. (2분이 지나면 소피는 이미 보물의 위치를 알지만, 그곳에 도달하려면 여전히 탐침이 필요하다.)