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 自动生成