题目描述

让我们继续$\text{JC}$和$\text{DZY}$的故事。

• “你是我的小丫小苹果，怎么爱你都不嫌多！”
• “点亮我生命的火，火火火火火！”

话说$\text{JC}$历经艰辛来到了城市$\text B$，但是由于他的疏忽$\text{DZY}$偷走了他的小苹果！没有小苹果怎么听歌！他发现邪恶的$\text{DZY}$把他的小苹果藏在了一个迷宫里。$\text{JC}$在经历了之前的战斗后他还剩下$hp$点血。开始$\text{JC}$在$1$号点，他的小苹果在N号点。$\text{DZY}$在一些点里放了怪兽。当$\text{JC}$每次遇到位置在$i$的怪兽时他会损失$A_i$点血。当$\text{JC}$的血小于等于$0$时他就会被自动弹出迷宫并且再也无法进入。

但是$\text{JC}$迷路了，他每次只能从当前所在点出发等概率的选择一条道路走。所有道路都是双向的，一共有$m$条，怪兽无法被杀死。现在$\text{JC}$想知道他找到他的小苹果的概率。

P.S.：$\green{\text{都知道这个系列是提高组模拟赛，所以这是一道送分题balabala}}$

输入格式

第一行三个整数表示$n$，$m$，$hp$。接下来一行整数，第$i$个表示$\text{JC}$到第$i$个点要损失的血量。保证第$1$个和$n$个数为$0$。接下来$m$行每行两个整数$a,b$表示$ab$间有一条无向边。

输出格式

仅一行，表示$\text{JC}$找到他的小苹果的期望概率，保留八位小数。

样例

3 3 2
0 1 0
1 2
1 3
2 3

0.87500000

数据范围与约定

对于$100\%$的数据：$2\le n\le 150，hp\le 10000，m\le 5000$，保证图联通。