좀비 섬

문제

JOI 군이 살고 있는 섬이 좀비에게 침략당하고 말았다. JOI 군은 섬에서 가장 안전한 대피 장소로 지정되어 있는 대피소로 도망치기로 했다.

JOI 군이 살고 있는 섬은 마을 1 부터 마을 N 까지의 N 개의 마을로 이루어져 있고, 마을과 마을은 도로로 연결되어 있다. 섬에는 M 개의 도로가 있으며, 모든 도로는 서로 다른 2 개의 마을을 연결한다. JOI 군은 도로를 양방향으로 자유롭게 이동할 수 있지만, 도로 이외의 경로로 한 마을에서 다른 마을로 갈 수는 없다.

몇몇 마을은 좀비에게 점령되어 있어 방문할 수 없다. 좀비에게 점령된 마을에서 S 개 이하의 도로를 사용하여 도달할 수 있는 마을을 위험한 마을이라고 한다. 그 밖의 마을을 위험하지 않은 마을이라고 한다.

JOI 군의 집은 마을 1 에 있고, 대피할 대피소는 마을 N 에 있다. 마을 1, 마을 N 은 좀비에게 점령되어 있지 않다. 섬의 도로는 이동하는 데 시간이 걸리므로, JOI 군은 마을을 이동할 때마다 이동한 마을에서 하룻밤 숙박해야 한다. JOI 군은 위험하지 않은 마을에서 숙박하는 경우에는 숙박비가 P 원인 싼 숙소에 묵지만, 위험한 마을에서 숙박하는 경우에는 보안 서비스가 우수한 숙박비가 Q 원인 고급 숙소에 묵는다. JOI 군은 가능한 한 숙박비가 싸지도록 이동하여 마을 N 까지 대피하고 싶다. 마을 1 이나 마을 N 에서는 숙박할 필요가 없다.

JOI 군이 마을 1 에서 마을 N 까지 이동할 때 필요한 숙박비 합계의 최솟값을 구하는 프로그램을 작성하시오.

입력

입력은 2 + K + M 줄로 이루어진다.

1 번째 줄에는 네 정수 N, M, K, S (2 ≦ N ≦ 100000, 1 ≦ M ≦ 200000, 0 ≦ K ≦ N - 2, 0 ≦ S ≦ 100000) 가 공백으로 구분되어 쓰여 있다. 이는 섬이 N 개의 마을과 M 개의 도로로 이루어져 있고, N 개의 마을 중 K 개의 마을이 좀비에게 점령되어 있으며, 좀비에게 점령된 마을에서 S 개 이하의 도로를 사용하여 도달할 수 있는 마을을 위험한 마을이라고 부름을 나타낸다.

2 번째 줄에는 두 정수 P, Q (1 ≦ P ＜ Q ≦ 100000) 가 공백으로 구분되어 쓰여 있다. 이는 JOI 군이 위험하지 않은 마을에서는 숙박비가 P 원인 숙소에 묵고, 위험한 마을에서는 숙박비가 Q 원인 숙소에 묵음을 나타낸다.

이어지는 K 줄 중 i 번째 줄 (1 ≦ i ≦ K) 에는 정수 $C_{i}$ (2 ≦ $C_{i}$ ≦ N - 1) 가 쓰여 있다. 이는 마을 $C_{i}$ 가 좀비에게 점령되어 있음을 나타낸다. $C_{1}$, ..., $C_{K}$ 는 모두 다르다.

이어지는 M 줄 중 j 번째 줄 (1 ≦ j ≦ M) 에는 두 정수 $A_{j}$, $B_{j}$ (1 ≦ $A_{j}$ ＜ $B_{j}$ ≦ N) 가 공백으로 구분되어 쓰여 있다. 이는 마을 $A_{j}$ 와 마을 $B_{j}$ 사이에 도로가 존재함을 나타낸다. 같은 ($A_{j}$, $B_{j}$) 쌍이 2 번 이상 쓰여 있는 경우는 없다.

주어지는 입력 데이터에서는 마을 1 에서 마을 N 까지 좀비에게 점령되어 있지 않은 마을만을 지나 이동할 수 있음이 보장된다.

출력

JOI 군이 마을 1 에서 마을 N 까지 이동할 때 필요한 숙박비 합계의 최솟값을 한 줄에 출력한다.

출력이 32 비트 부호 있는 정수의 범위에 들어간다고 할 수는 없음에 주의하시오.

예제 입력 1

13 21 1 1
1000 6000
7
1 2
3 7
2 4
5 8
8 9
2 5
3 4
4 7
9 10
10 11
5 9
7 12
3 6
4 5
1 3
11 12
6 7
8 11
6 13
7 8
12 13

예제 출력 1

11000

예제 1 은 다음 그림에 대응한다. 원은 마을을, 선은 도로를 나타낸다.

이 경우, 마을 3, 마을 4, 마을 6, 마을 8, 마을 12 가 위험한 마을이다.

다음과 같은 순서로 마을을 이동하면 숙박비의 합계를 최소로 할 수 있다.

• 마을 1 에서 마을 2 로 간다. 마을 2 에서 숙박비가 1000 원인 싼 숙소에 숙박한다.
• 마을 2 에서 마을 5 로 간다. 마을 5 에서 숙박비가 1000 원인 싼 숙소에 숙박한다.
• 마을 5 에서 마을 9 로 간다. 마을 9 에서 숙박비가 1000 원인 싼 숙소에 숙박한다.
• 마을 9 에서 마을 10 으로 간다. 마을 10 에서 숙박비가 1000 원인 싼 숙소에 숙박한다.
• 마을 10 에서 마을 11 로 간다. 마을 11 에서 숙박비가 1000 원인 싼 숙소에 숙박한다.
• 마을 11 에서 마을 12 로 간다. 마을 12 에서 숙박비가 6000 원인 고급 숙소에 숙박한다.
• 마을 12 에서 마을 13 으로 간다. 마을 13 에서는 숙박하지 않는다.

JOI 군이 이러한 경로로 이동했을 때 숙박비의 합계는 11000 원이 되므로, 11000 을 출력한다.

예제 입력 2

21 26 2 2
1000 2000
5
16
1 2
1 3
1 10
2 5
3 4
4 6
5 8
6 7
7 9
8 10
9 10
9 11
11 13
12 13
12 15
13 14
13 16
14 17
15 16
15 18
16 17
16 19
17 20
18 19
19 20
19 21

예제 출력 2

15000