Balanced Weight Redistribution

You are given an undirected graph with n vertices and m edges. The graph may contain self‐loops and multiple edges, and it can be disconnected. Initially each vertex is assigned a positive real weight. You are also given two positive integers p and q with p < q.

Your task is to reassign the weights to the vertices subject to the following conditions:

1. The total sum of the weights remains unchanged.
2. For every edge connecting vertices u and v, if their new weights are a_u and a_v then the ratio between the larger and the smaller one does not exceed x. In other words, \(\max(a_u,a_v)/\min(a_u,a_v) \le x\). Note that by definition \(x \ge 1\).
3. For every vertex i, its new weight a_i must be at least \(\frac{p}{q}\) times its original weight, i.e. \(a_i \ge \frac{p}{q} \cdot w_i\).

The goal is to determine the minimum value of \(x \ge 1\) such that for any possible initial assignment of vertex weights, there exists a redistribution satisfying the three conditions above.

Note: If the graph has no edges, then no ratio condition is imposed and the answer is trivially 1. Otherwise, an adversary may choose the initial weights on some edge extremely imbalanced. In such a worst‐case on a single edge with vertices having weights \(w_u\) and \(w_v\), it can be shown that if we denote \(r = \frac{p}{q}\), then when \(r \le \tfrac12\) the weights can be rebalanced to make all adjacent pairs equal (i.e. \(x=1\)), and when \(r > \tfrac12\) the minimum feasible value is
\[ x = \frac{r}{1 - r} = \frac{p}{q - p}. \]

inputFormat

The input is given in the following format:

 n m p q
 w[1] w[2] ... w[n]
 u1 v1
 u2 v2
 ...
 um vm

• The first line contains four numbers: an integer n (number of vertices), an integer m (number of edges), and two integers p and q (with p < q).
• The second line contains n positive real numbers representing the initial weights of the vertices.
• Each of the next m lines contains two integers \(u\) and \(v\) (1-indexed) indicating an edge between vertices \(u\) and \(v\). There may be self-loops and multiple edges.

outputFormat

Output the minimum value of x (a real number) that satisfies the conditions. Print the result with 6 decimal places.

Note: When the graph has no edges, output 1. Otherwise, if \(r=\frac{p}{q} \le \tfrac12\) then the answer is 1, and if \(r>\tfrac12\) then the answer is \(\frac{p}{q-p}\).

sample

3 0 1 2
1.0 2.0 3.0

1.000000