题目描述

There are $N$ cities numbered from $1$ to $N$. There is a bi-directional road connecting city $i$ to city $i + 1$ for $1 \leq i < N$ and city $N$ to city $1$. Each road takes $1$ day to travel.

Due to a pandemic situation, there are $M$ cities that impose a quarantine order for any visitors to mitigate the pandemic spread in those cities. Specifically, whenever someone visits city $C_i$, they will be quarantined for a duration of exactly $T_i$ days in a government-provided facility in that city. The order applies to any visitor including those who don't intend to stay in that city, e.g., only transiting.

Nawan is a rising young musician who already has $K$ die-hard fans. The $i^{th}$ fan lives in city $D_i$, and surprisingly enough, none of the fans live in a city that imposes a quarantine order for visitors. Nawan has just released an album and now he wants to hold concerts for his die-hard fans. Despite rejections from his team, Nawan insists that the concert must be held live and in person; he believes that he wouldn't be able to convey his "musical feeling" to his fans through a virtual concert.

After considering the budget and their resource, Nawan and his team agree to hold at most $P$ concerts. Moreover, These concerts can only be held in cities that are not imposing any quarantine order for visitors. Nawan has contacted all of his fans and each of them agrees to attend only $1$ concert. The only remaining issue is in choosing the cities where Nawan should have a concert.

Each of the fans will attend a concert in which the venue requires the minimum travel time from their city. Each concert venue has no maximum capacity. Nawan wishes to hold the concerts in at most $P$ cities such that the longest travel time among all of his fans is as minimum as possible. Since Nawan needs to practice and prepare for the concerts, he asked you to choose the cities in which he should have a concert such that the longest required travel time by any fan is as minimum as possible; you only need to output the minimum longest travel time.

For example, let $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\}$, and $P = 2$. In this example, the concert venues should be in city $5$ and city $10$ with a longest travel time of only $4$ days.

• The $1^{st}$ fan at city $2$ will go to the concert at city $10$, i.e. $2 \rightarrow 1$ (quarantined for $2$ days) $\rightarrow 10$, for a total travel time of $4$ days.
• The $2^{nd}$ fan at city $5$ will go to the concert at city $5$ where no travel is needed.
• The $3^{rd}$ fan at city $8$ will go to the concert at city $10$. i.e. $8 \rightarrow 9 \rightarrow 10$, for a total travel time of $2$ days.

输入格式

Input begins with a line containing four integers $N$ $M$ $K$ $P$ ($1 \leq M < N \leq 200\,000$; $1 \leq K, P \leq N - M$) representing the number of cities, the number of cities that impose a quarantine order, the number of Nawan's die-hard fans, and the maximum number of concerts to be held, respectively. The next $M$ lines each contains two integers $C_i$ $T_i$ ($1 \leq C_i \leq N$; $1 \leq T_i \leq 200\,000$) representing the city that has a quarantine order and its quarantine duration, respectively. It is guaranteed that all $C_i$ are unique. The last line contains $K$ integers $D_i$ ($1 \leq D_i \leq N$) representing the city in which the $i^{th}$ fan lives in. It is guaranteed that no fan lives in a city that imposes a quarantine order for visitors, and all fans live in a different city.

输出格式

Output contains an integer in a line representing the minimum longest travel time needed by any fan to reach a concert venue.

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

提示

Explanation for the sample input/output #2

Nawan can hold a private concert for each of his fans, i.e. the concert venues should be in cities $2$, $4$, and $7$.