说明

有 $N$ 座城市，编号从 $1$ 到 $N$。对于 $1 \leq i < N$，有一条双向道路连接城市 $i$ 和城市 $i+1$，并且还有一条道路连接城市 $N$ 和城市 $1$。每条道路需要 $1$ 天时间通行。

由于疫情，有 $M$ 座城市对所有访客实施隔离令，以减缓疫情在这些城市的传播。具体来说，每当有人访问城市 $C_i$，他们将被强制在该城市政$$府提供的设施中隔离恰好 $T_i$ 天。该规定适用于任何访客，包括那些不打算在该城市停留的人（例如仅仅过境）。

纳万是一位崭露头角的年轻音乐家，他拥有 $K$ 位铁杆粉丝。第 $i$ 位粉丝居住在城市 $D_i$，并且令人惊讶的是，没有粉丝居住在实施访客隔离令的城市。纳万刚刚发布了一张新专辑，现在他想为他的铁杆粉丝们举办演唱会。尽管遭到团队的反对，纳万坚持认为演唱会必须现场面对面举行；他相信通过虚拟演唱会无法向粉丝传达他的“音乐感觉”。

在考虑预算和资源后，纳万和他的团队同意最多举办 $P$ 场演唱会。此外，这些演唱会只能在未实施任何访客隔离令的城市举办。纳万已联系了所有粉丝，每位粉丝同意只参加 $1$ 场演唱会。剩下的唯一问题是选择纳万应该举办演唱会的城市。

每位粉丝将参加从他们所在城市出发所需旅行时间最短的那场演唱会。每个演唱会场地没有最大容量限制。纳万希望最多在 $P$ 个城市举办演唱会，使得所有粉丝中最大的旅行时间尽可能小。由于纳万需要练习和准备演唱会，他请你选择举办演唱会的城市，使得任何粉丝所需的最长旅行时间尽可能小；你只需要输出这个最小化的最长旅行时间。

例如，设 $N = 10$，$M = 4$，$C_{1..4} = \{1, 4, 6, 7\}$，$T_{1..4} = \{2, 4, 2, 5\}$，$K = 3$，$D_{1..3} = \{2, 5, 8\}$，$P = 2$。在此例中，演唱会场地应选在城市 $5$ 和城市 $10$，最长旅行时间仅为 $4$ 天。

• 位于城市 $2$ 的第 $1$ 位粉丝将前往城市 $10$ 的演唱会，路线为 $2 \rightarrow 1$（隔离 $2$ 天）$\rightarrow 10$，总旅行时间为 $4$ 天。
• 位于城市 $5$ 的第 $2$ 位粉丝将前往城市 $5$ 的演唱会，无需旅行。
• 位于城市 $8$ 的第 $3$ 位粉丝将前往城市 $10$ 的演唱会，路线为 $8 \rightarrow 9 \rightarrow 10$，总旅行时间为 $2$ 天。

输入格式

输入第一行包含四个整数 $N$、$M$、$K$ 和 $P$（$1 \leq M < N \leq 200\,000$；$1 \leq K, P \leq N - M$），分别表示城市数量、实施隔离令的城市数量、纳万的铁杆粉丝数量以及最多举办的演唱会数量。接下来 $M$ 行，每行包含两个整数 $C_i$ 和 $T_i$（$1 \leq C_i \leq N$；$1 \leq T_i \leq 200\,000$），分别表示实施隔离令的城市及其隔离时长。保证所有 $C_i$ 互不相同。最后一行包含 $K$ 个整数 $D_i$（$1 \leq D_i \leq N$），表示第 $i$ 位粉丝所在的城市。保证没有粉丝居住在实施访客隔离令的城市，且所有粉丝居住的城市互不相同。

输出格式

输出一行一个整数，表示任何粉丝到达演唱会场地所需的最短最长旅行时间。

10 4 3 2
1 2
4 4
6 2
7 5
2 5 8

4

8 1 3 5
1 5
4 2 7

0

5 2 2 1
1 14
2 14
3 5

1

提示

样例 #2 解释

纳万可以为每位粉丝举办一场私人演唱会，即演唱会场地应选在城市 $2$、$4$ 和 $7$。

翻译由 DeepSeek 完成