Electric Car

Vytautas wants to visit his friend Vytis in his brand-new, shiny electric car. Both friends live in Bitland, which consists of $N$ cities numbered from $1$ to $N$. Vytautas lives in city $1$, and Vytis lives in city $N$. The cities are connected by $M$ two-way roads.

Along the way, Vytautas may have to stop and charge the car. If city $i$ has a charging station, it charges $c_i$ kWh per hour. Vytautas always charges for a whole number of hours (this makes it easier to plan his time). The battery capacity is $K$ kWh, and the charge never exceeds $K$. If the battery becomes full before the hour is over, Vytautas simply leaves the car plugged in until the hour ends.

Driving along any single road takes exactly $1$ hour and consumes $L$ kWh. Because the car is brand new, the battery is empty at the start of the trip.

What is the shortest time in which Vytautas can travel from city $1$ to city $N$, given that every charging session must last a whole number of hours?

The first line contains four integers:

• $N$ — the number of cities;
• $M$ — the number of roads;
• $K$ — the battery capacity of the car;
• $L$ — the amount of energy the car consumes to drive along one road (one hour).

The second line contains $N$ integers $c_i$ ($0 \le c_i \le K$) — city $i$ can charge $c_i$ kWh per hour (if $c_i = 0$, there is no charging station in that city).

Each of the next $M$ lines describes a road by its two endpoint cities $a_i$ and $b_i$ ($1 \le a_i, b_i \le N$).

Output a single integer — the minimum time needed to travel from city $1$ to city $N$. Output $-1$ if the trip is impossible.

• $2 \le N \le 100\,000$
• $1 \le M \le 100\,000$
• $1 \le K, L \le 100$
• $a_i \ne b_i$
• there is at most one direct road between any two cities.