JOI 군이 사는 섬이 좀비에게 점령당했다. JOI 군은 섬에서 가장 안전한 대피 장소로 정해진 대피소로 도망가려 한다. 섬에는 마을 \(1\)부터 마을 \(N\)까지 \(N\)개의 마을이 있고, 마을은 길로 이어져 있다. 길은 \(M\)개이고, 각 길은 서로 다른 두 마을을 잇는다. JOI 군은 길을 양쪽으로 자유롭게 다닐 수 있지만, 길 밖으로는 마을에서 다른 마을로 갈 수 없다. 몇몇 마을은 좀비가 장악해 들어갈 수 없다. 좀비가 장악한 마을에서 길 \(S\)개 이하로 닿을 수 있는 마을을 위험한 마을이라 하고, 그렇지 않은 마을을 위험하지 않은 마을이라 한다. JOI 군의 집은 마을 \(1\)에 있고, 대피소는 마을 \(N\)에 있다. 마을 \(1\)과 마을 \(N\)은 좀비가 장악하지 않았다. 길을 이동하는 데 시간이 걸리므로, JOI 군은 마을을 옮길 때마다 도착한 마을에서 하룻밤을 묵어야 한다. 위험하지 않은 마을에서는 숙박비 \(P\)원인 싼 여관에 묵고, 위험한 마을에서는 보안이 좋은 숙박비 \(Q\)원인 고급 여관에 묵는다. JOI 군은 숙박비가 되도록 적게 들게 마을 \(N\)까지 피하고 싶다. 마을 \(1\)과 마을 \(N\)에서는 묵지 않아도 된다. JOI 군이 마을 \(1\)에서 마을 \(N\)까지 갈 때 필요한 숙박비 합의 최솟값을 구하라. |
입력은 다음 형식으로 주어진다.
\(N\) \(M\) \(K\) \(S\)
\(P\) \(Q\)
\(C_1\)
\(\vdots\)
\(C_K\)
\(A_1\) \(B_1\)
\(\vdots\)
\(A_M\) \(B_M\)
- 입력은 \(2+K+M\)줄이다.
- 첫째 줄에 정수 \(N\), \(M\), \(K\), \(S\)가 공백 하나로 구분되어 주어진다. 섬에 마을 \(N\)개와 길 \(M\)개가 있고, 그중 \(K\)개 마을이 좀비에게 장악되었으며, 좀비가 장악한 마을에서 길 \(S\)개 이하로 닿는 마을을 위험한 마을이라 함을 나타낸다.
- 둘째 줄에 정수 \(P\), \(Q\)가 공백 하나로 구분되어 주어진다. 위험하지 않은 마을에서는 숙박비 \(P\)원, 위험한 마을에서는 숙박비 \(Q\)원인 여관에 묵음을 나타낸다.
- 이어지는 \(K\)줄 중 \(i\)번째 줄(\(1 \le i \le K\))에 정수 \(C_i\)가 주어지고, 마을 \(C_i\)가 좀비에게 장악되었음을 나타낸다. \(C_1, \ldots, C_K\)는 모두 다르다.
- 이어지는 \(M\)줄 중 \(j\)번째 줄(\(1 \le j \le M\))에 정수 \(A_j\), \(B_j\)가 공백 하나로 구분되어 주어지고, 마을 \(A_j\)와 마을 \(B_j\) 사이에 길이 있음을 나타낸다. 같은 \((A_j, B_j)\)가 두 번 이상 나오지 않는다.
- \(2 \le N \le 100000\)
- \(1 \le M \le 200000\)
- \(0 \le K \le N-2\)
- \(0 \le S \le 100000\)
- \(1 \le P < Q \le 100000\)
- \(2 \le C_i \le N-1\)
- \(1 \le A_j < B_j \le N\)
- 마을 \(1\)에서 마을 \(N\)까지 좀비가 장악하지 않은 마을만 지나 갈 수 있음이 보장된다.
- 입력되는 값은 모두 정수이다.
다음 형식으로 출력한다.
첫째 줄에, JOI 군이 마을 \(1\)에서 마을 \(N\)까지 갈 때 필요한 숙박비 합의 최솟값을 출력한다.
- 출력하는 값이 \(32\)비트 부호 있는 정수 범위에 들어가지 않을 수 있다.
이 경우 마을 \(3, 4, 6, 8, 12\)가 위험한 마을이다. 마을을 \(1 \to 2 \to 5 \to 9 \to 10 \to 11 \to 12 \to 13\) 순으로 가면 숙박비 합이 최소가 된다. 마을 \(2, 5, 9, 10, 11\)에서는 \(1000\)원짜리 싼 여관에, 마을 \(12\)에서는 \(6000\)원짜리 고급 여관에 묵고 마을 \(13\)에서는 묵지 않는다. 합은 \(11000\)원이다.