AT_joi2016yo_e ゾンビ島 (Zombie Island)

JOI 君居住的岛屿遭遇了僵尸入侵。他决定逃到岛上设定的最安全的避难所。 岛上共有 $N$ 个城镇，从 $1$ 到 $N$ 编号，这些城镇通过 $M$ 条道路相互连接。每条道路都连接两个不同的城镇。JOI 君可以在这些道路上自由往返，但不能随意穿越道路以外的地方。 城市中有一些被僵尸占领，无法前往。从被僵尸占领的城镇，通过不超过 $S$ 条道路可以到达的城镇称为“危险城镇”，其余的称为“安全城镇”。 JOI 君的家在城镇 $1$，而避难所位于城镇 $N$。这两个城镇都没有被僵尸占领。由于每次在城镇之间移动需要时间，JOI 君必须在每个目的地城镇过夜。在“安全城镇”过夜的费用较低，仅为 $P$ 元，而在“危险城镇”过夜的费用较高，为 $Q$ 元。JOI 君的目标是以最低的住宿费用从城镇 $1$ 到达城镇 $N$。在城镇 $1$ 和城镇 $N$ 无需过夜。 请计算 JOI 君从家到避难所所需的最少住宿费用。

输入包含 $2 + K + M$ 行。 - 第 $1$ 行：四个整数 $N,\ M,\ K,\ S$，分别表示 $N$ 个城镇，$M$ 条道路，$K$ 个被僵尸占领的城镇，以及“危险城镇”的距离界限 $S$。 ($2 \leq N \leq 100\,000$，$1 \leq M \leq 200\,000$，$0 \leq K \leq N - 2$，$0 \leq S \leq 100\,000$) - 第 $2$ 行：两个整数 $P, Q$，分别表示在“安全城镇”的过夜费用和在“危险城镇”的过夜费用。 ($1 \leq P < Q \leq 100\,000$) - 接下来的 $K$ 行：每行一个整数 $C_i$，表示被僵尸占领的城镇编号。 ($2 \leq C_i \leq N - 1$) - 接下来的 $M$ 行：每行两个整数 $A_j, B_j$，表示存在一条连接城镇 $A_j$ 和 $B_j$ 的道路。($1 \leq A_j < B_j \leq N$) 输入数据保证从城镇 $1$ 可以通过未被僵尸占领的城镇路径到达城镇 $N$。

输出 JOI 君从城镇 $1$ 到城镇 $N$ 最低住宿费用的总和。 请注意，输出结果可能超出 $32$ 位有符号整数的范围。 ### 样例解释 以下示例如图所示，圆圈代表城镇，线条代表道路： 在此图中，城镇 $3$，$4$，$6$，$8$ 和 $12$ 被视为“危险城镇”。以下路径可使住宿费用最低： - 从城镇 $1$ 到城镇 $2$，在城镇 $2$ 花费 $1,000$ 元。 - 从城镇 $2$ 到城镇 $5$，在城镇 $5$ 花费 $1,000$ 元。 - ...（依此类推） 按照这样的步骤，JOI 君花费总计为 $11,000$ 元，因此输出 $11,000$。 **本翻译由 AI 自动生成**

### Sample Explanation 1 入出力例 $ 1 $ は，以下の図に対応している．円は町を，線は道路を表す． !\[2016-yo-t5-fig01.png\](https://img.atcoder.jp/joi2016yo/2016-yo-t5-fig01.png) この場合，町 $ 3 $，町 $ 4 $，町 $ 6 $，町 $ 8 $，町 $ 12 $ が危険な町である． 以下のような順番で町を移動すると，宿泊費の合計を最小にできる． - 町 $ 1 $ から町 $ 2 $ に行く．町 $ 2 $ で宿泊費が $ 1\,000 $ 円の安い宿に宿泊する． - 町 $ 2 $ から町 $ 5 $ に行く．町 $ 5 $ で宿泊費が $ 1\,000 $ 円の安い宿に宿泊する． - 町 $ 5 $ から町 $ 9 $ に行く．町 $ 9 $ で宿泊費が $ 1\,000 $ 円の安い宿に宿泊する． - 町 $ 9 $ から町 $ 10 $ に行く．町 $ 10 $ で宿泊費が $ 1\,000 $ 円の安い宿に宿泊する． - 町 $ 10 $ から町 $ 11 $ に行く．町 $ 11 $ で宿泊費が $ 1\,000 $ 円の安い宿に宿泊する． - 町 $ 11 $ から町 $ 12 $ に行く．町 $ 12 $ で宿泊費が $ 6\,000 $ 円の高級宿に宿泊する． - 町 $ 12 $ から町 $ 13 $ に行く．町 $ 13 $ では宿泊しない． JOI 君がこのような経路で移動したとき，宿泊費の合計は $ 11\,000 $ 円になるので，$ 11\,000 $ を出力する． - - - - - -