题目描述

有 $V$ 个景点，编号为 $1$ ~ $V$。每个景点有一个观赏指数，景点 $i$ 的观赏指数为 $W_i$。

有 $E$ 条单向道路。可能有从一个景点出发又回到这个景点的道路（自环），但从一个景点出发到另一个景点之间最多有一条道路（无重边）。

小 A 准备从景点 $S$ 开启他的徒步之旅。

走路是要耗费体力的。小 A 的初始体力值为 $1$。每走一条道路，他的体力值会下降为他在该条道路起点处体力值的 $p (0 < p < 1)$ 倍。

观赏风景会使人的心情愉悦。小 A 的初始心情愉悦值为 $0$。每当小 A 来到某个景点时，他在该景点的心情愉悦值就会增加，增加的值为他当时的体力值乘以该景点的观赏指数。

小 A 有充足的时间，他可以一直旅行到永久。他当然想使自己最后的心情愉悦值尽可能大。为此，他找到了你，请你帮助他设计合适的旅行路线。

你能帮助他吗？你只需要输出他最后的心情愉悦值的最大可能值，四舍五入保留 $1$ 位小数。

输入格式

第 $1$ 行：两个整数 $V, E$。

第 $2$ 行：$V$ 个实数 $W_i$。

第 $3$ 行：一个整数 $S$。

第 $4$ 行：$1$ 个实数 $p$。

最后 $E$ 行：每行两个整数 $a_i, b_i$，表示从 $a_i$ 到 $b_i$ 有一条有向边。

输出格式

一个实数，四舍五入保留 $1$ 位小数，表示小 A 最后的心情愉悦值的最大可能值。

样例输入

5 5 
5.0 2.0 1.0 3.0 4.0 
1 
0.6
1 2 
2 3 
3 4 
4 2 
4 5

样例输出

7.8

提示

$10\% 的数据： V ≤ 10， E ≤ 10$

$100\% 的数据： V ≤ 100， E ≤ 1000， 0 < p < 1， 0 ≤ W_i ≤ 100， 1 ≤ a_i, b_i ≤ V， 1 ≤ S ≤ V$

在测试数据中，实数的输入保留 $12$ 位有效数字。