There is a directed graph $G$ with $n$ vertices $1, 2, \dots, n$, where each vertex $i$ has a weight $w(i)$. An ant starts at a given vertex $v_0$ and crawls along the edges of $G$. Initially, its stamina is $1$. Each time it traverses an edge, its stamina is multiplied by $\rho$, where $\rho$ is a given positive constant less than $1$. The happiness of the ant when it reaches a vertex is the product of its current stamina and the weight of that vertex.

We define $H$ as the sum of the ant's happiness values along its path. Clearly, $H$ may vary depending on the path taken. Little Z is interested in the maximum possible value of $H$. Can you help him calculate it? Note that the path length of the ant may be infinite.

Input

The input file contains several lines, with numbers on each line separated by a space.

The first line contains two positive integers $n$ and $m$, representing the number of vertices and the number of edges in $G$, respectively.

The second line contains $n$ non-negative real numbers, representing the weights of the $n$ vertices $w(1), w(2), \dots, w(n)$ in order.

The third line contains a positive integer $v_0$, representing the given starting vertex.

The fourth line contains a real number $\rho$, representing the given positive constant less than $1$.

The next $m$ lines each contain two positive integers $x$ and $y$, representing a directed edge $\langle x, y \rangle$ in $G$. There may be self-loops, but there are no multiple edges.

Output

The output file contains a single real number, which is the maximum possible value of $H$, rounded to one decimal place.

Examples

Input 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

Output 1

18.0

Note

When the ant's path is $1 \to 2 \to 3 \to 4 \to 2 \to 3 \to 4 \to \dots \to 2 \to 3 \to 4 \to \dots$, $H = 10.0 + 8.0 \times 0.5 + 8.0 \times 0.5^2 + \dots$. It can be proven that the sum of this infinite sequence is $18.0$, and this is the maximum value of $H$.

Additionally, if $w(5)$ in this example were changed to $17.0$ while other data remained the same, then for the path $1 \to 2 \to 3 \to 4 \to 5$, $H = 18.0625$. It can be proven that this is the maximum value of $H$ in that case.

Constraints

For $20\%$ of the data, $\rho \le 0.5$; For another $20\%$ of the data, it is guaranteed that the maximum value of $H$ is achieved on a finite path; For $100\%$ of the data, $n \le 100$, $m \le 1000$, $\rho \le 1 - 10^{-6}$, $w(i) \le 100$ ($i = 1, 2, \dots, n$).