Description

There is a directed graph $G$ with $n$ vertices $1, 2, \cdots, n$, and the weight of vertex $i$ is $w(i)$.

An ant starts from a given starting 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$. When the ant reaches a vertex, its happiness is the product of its current stamina and the weight of that vertex.

We denote the total happiness along the crawling path by $H$. Clearly, for different crawling paths, the value of $H$ may differ. Xiao Z is interested in the maximum possible value of $H$. Can you help compute it? Note that the length of the ant’s path may be infinite.

Input Format

Numbers on each line are separated by a single space.

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

The second line contains $n$ non-negative real numbers, representing the vertex weights $w(1), w(2), \cdots, w(n)$.

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

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

Each of the next $m$ lines contains two positive integers $x, y$, indicating that $(x, y)$ is a directed edge of $G$. Self-loops may exist, but there are no multiple edges.

Output Format

Output a single real number: the maximum possible value of $H$, rounded to one decimal place.

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

Hint

For $100\%$ of the testdata, $1 \leq n \le 100$, $1 \leq m \le 1000$, $0 < \rho \le 1 - 10^{-6}$, $0 \leq w(i) \leq 100$.

Translated by ChatGPT 5