[Ctsc2011]幸福路径

给定一张包含 $n$ 个顶点的有向图 $G$，顶点编号为 $1,2,\ldots,n$，顶点 $i$ 的权值为 $w(i)$。

一只蚂蚁从给定的起点 $v_0$ 出发，沿图 $G$ 中的有向边爬行。开始时，它的体力为 $1$。每爬过一条边，它的体力都会变为原来的 $\rho$ 倍，其中 $\rho$ 是一个给定的、小于 $1$ 的正常数。

蚂蚁到达某个顶点时获得的幸福度，等于它此时的体力与该顶点权值的乘积。将蚂蚁在整条爬行路径上获得的幸福度总和记为 $H$。不同的爬行路径可能得到不同的 $H$，请计算 $H$ 的最大可能值。

注意，蚂蚁爬行的路径长度可能是无限的。

输入格式

输入数据中，同一行内相邻两个数之间用一个空格分隔。

第一行包含两个正整数 $n,m$，分别表示图 $G$ 的顶点数和边数。

第二行包含 $n$ 个非负实数，依次表示各顶点的权值 $w(1),w(2),\ldots,w(n)$。

第三行包含一个正整数 $v_0$，表示蚂蚁的起点。

第四行包含一个实数 $\rho$，表示给定的小于 $1$ 的正常数。

接下来 $m$ 行，每行包含两个正整数 $x,y$，表示图 $G$ 中存在一条从顶点 $x$ 指向顶点 $y$ 的有向边。

图中可能存在自环，但不存在重边。

输出格式

输出一个实数，表示 $H$ 的最大可能值。答案四舍五入到小数点后 $1$ 位。

样例输入

5 5
10.0 8.0 8.0 8.0 15.0
1
0.5
1 2
2 3
3 4
4 2
4 5

样例输出

18.0

数据范围

• $n\le 100$；
• $m\le 10^3$；
• $\rho\le 1-10^{-6}$；
• 对于所有 $i=1,2,\ldots,n$，均有 $w(i)\le 100$。

来源与许可

本题为 CTSC 2011 试题「幸福路径」，题面与测试数据整理自 BZOJ。

样例 1

输入

5 5
10.0 8.0 8.0 8.0 15.0
1
0.5
1 2
2 3
3 4
4 2
4 5

输出

18.0