Maximum Discounted Happiness in a Directed Graph

An ant is traversing a directed graph \(G\) with \(n\) vertices labeled \(1,2,\dots,n\). Each vertex \(i\) has an associated weight \(w(i)\). The ant starts at a given vertex \(v_0\) with an initial energy of \(1\). Every time the ant traverses an edge, its energy is multiplied by a given constant \(\rho\) where \(0<\rho<1\). When the ant arrives at a vertex, it gains happiness equal to the product of its current energy and the vertex's weight. If the ant follows a path \(v_0, v_1, v_2, \dots\), then the total happiness is computed as

[ H = 1 \cdot w(v_0) + \rho \cdot w(v_1) + \rho^2 \cdot w(v_2) + \cdots ]

Your task is to compute the maximum possible total happiness \(H\) the ant can achieve if it can traverse an arbitrarily long (even infinite) path. It is guaranteed that the discount factor \(\rho\) makes the infinite series convergent.

inputFormat

The input consists of the following:

1. The first line contains four values: \(n\) \(m\) \(v_0\) \(\rho\), where \(n\) is the number of vertices, \(m\) is the number of directed edges, \(v_0\) (\(1 \le v_0 \le n\)) is the starting vertex, and \(\rho\) is a real number satisfying \(0 < \rho < 1\).
2. The second line contains \(n\) numbers representing the weights \(w(1), w(2), \dots, w(n)\) of the vertices.
3. Each of the next \(m\) lines contains two integers \(u\) and \(v\), indicating a directed edge from vertex \(u\) to vertex \(v\).

outputFormat

Output a single real number representing the maximum total happiness \(H\) achievable, starting from vertex \(v_0\). The answer will be considered correct if its absolute or relative error does not exceed \(10^{-6}\).

sample

3 3 1 0.5
1 2 3
1 2
2 3
1 3

2.75