Elden Ring: Boss Clearance Challenge

Professor Pang has become addicted to the game called Elden Ring. In this game, the world is represented by a connected undirected graph with \(n\) vertices numbered from \(1\) to \(n\) and \(m\) edges. The players start at vertex \(1\) and must eventually challenge the boss at vertex \(n\) (the Elden Beast) in order to finish the game.

However, the journey is not that simple. For every vertex \(i\) (except vertex \(1\)), there is a boss with an initial level \(l_i\). The player starts with level \(l_1\) (and vertex \(1\) has no boss). At the beginning of each day, every still active boss is promoted by \(B\) levels. Then, during that day, the player may travel from vertex \(1\) along a path whose intermediate vertices (all except the destination) have already been cleared (i.e. their bosses have been defeated) and challenge the boss at the destination vertex. The challenge is successful only if the player's current level is strictly greater than the boss's current level. A successful challenge eliminates the boss for good and increases the player's level by \(A\). Note that the player may challenge only one boss per day.

The task is to determine the minimum number of days required for Professor Pang to defeat the boss at vertex \(n\). If it is impossible to reach and defeat the boss at vertex \(n\) following the game’s rules, output -1.

Note: When a boss is challenged on day \(d\) (with days numbered starting at \(1\)), its current level is \(l_i + B \times d\), and the player's level at the start of day \(d\) is \(l_1 + A \times (d-1)\). The condition to defeat a boss at vertex \(i\) on day \(d\) is therefore:

[ l_1 + A \times (d-1) > l_i + B \times d. ]

inputFormat

The first line contains four integers \(n\), \(m\), \(A\) and \(B\) -- the number of vertices, the number of edges, the level increase after each victory, and the daily boss promotion level, respectively.

The second line contains \(n\) integers \(l_1, l_2, \dots, l_n\), where \(l_1\) is the starting level of the player, and for \(i \ge 2\), \(l_i\) is the initial level of the boss at vertex \(i\).

Then follow \(m\) lines, each containing two integers \(u\) and \(v\) representing an undirected edge between vertices \(u\) and \(v\>.

outputFormat

Output a single integer: the minimum number of days needed to defeat the boss at vertex \(n\). If it is impossible, output -1.

sample

3 2 5 1
10 5 20
1 2
2 3

-1