B. Mukhtar's Escape Plan
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Mukhtar is obsessed with octopuses and the deep sea.

At the Dead Sea, floating salt formations act as platforms connected by unusual water currents caused by natural conditions. Mukhtar uses these platforms to move around.

The platforms are represented as nodes of an undirected graph. If there is an edge between two platforms, then Mukhtar can directly move between them.

Unfortunately, some platforms are overcrowded with Salt creatures, so Mukhtar cannot stand on them.

Mukhtar has a special ability if an overcrowded platform $$$v$$$ lies between two platforms $$$u$$$ and $$$w$$$ such that there is an edge $$$(u, v)$$$ and an edge $$$(v, w)$$$, then he may skip platform $$$v$$$ and move directly from $$$u$$$ to $$$w$$$ without standing on $$$v$$$. Using this ability on platform $$$v$$$ costs $$$f(v)$$$.

Mukhtar starts at platform $$$1$$$ and wants to reach platform $$$n$$$.

However, his energy is limited. If the total cost of skipped platforms used in his path exceeds $$$c$$$, Mukhtar gets trapped and cannot escape until the conditions improve.

Determine whether Mukhtar can escape.

If there is no valid route from platform $$$1$$$ to platform $$$n$$$, or if the minimum possible total cost is greater than $$$c$$$, print $$$-1$$$. Otherwise, print the minimum total cost.

Input

The first line contains four integers $$$n$$$, $$$m$$$, $$$k$$$, and $$$c$$$ ($$$2 \le n, m \le 2 \cdot 10^5$$$, $$$0 \le k \le n-2$$$, $$$0 \le c \le 10^{18}$$$) — the number of platforms, the number of edges, the number of crowded platforms, and the maximum total skip cost Mukhtar can afford respectively.

The second line contains $$$k$$$ distinct integers — the indices of the crowded platforms.

The third line contains $$$n$$$ integers $$$f(1), f(2), \ldots, f(n)$$$ ($$$0 \le f(i) \le 10^9$$$), where $$$f(i)$$$ is the cost of skipping platform $$$i$$$.

Each of the next $$$m$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$), denoting an undirected edge between platforms $$$u$$$ and $$$v$$$.

It is guaranteed that platforms $$$1$$$ and $$$n$$$ are not crowded.

Output

Print the minimum possible total skip cost or $$$-1$$$ if its Impossible.

Examples
Input
6 6 2 10
3 5
0 0 8 0 2 0
1 2
2 3
3 6
2 4
4 5
5 6
Output
2
Input
5 3 1 10
3
0 0 4 0 0
1 2
2 3
4 5
Output
-1
Note

First test case explanation:

The crowded platforms are $$$3$$$ and $$$5$$$, with skip costs $$$f(3) = 8$$$ and $$$f(5) = 2$$$.

Mukhtar can use the allowed operation to skip platform $$$5$$$ while traversing a valid path, resulting in a total cost of $$$2$$$.