Concerto de Pandemic

Time limit2sMemory limit1024 MB

Summary

Place at most P concerts in non-quarantined cities on a cycle so the farthest fan's travel time is minimized, where each quarantined city passed through adds its delay.

Level: Medium7 of 10
Topics: Binary search, Greedy, Shortest path
Solved: No attempts yet

Statement

There are $N$ cities numbered from 1 to $N$ . A bidirectional road connects city $i$ and city $i + 1$ for $1 \le i < N$ , and city $N$ is connected to city 1 by a road as well. Each road takes 1 day to travel.

Due to a pandemic, $M$ cities impose a quarantine order on visitors. Whoever visits city $C_i$ is quarantined for exactly $T_i$ days in a government facility in that city. The order applies to all visitors, including those who only pass through the city without intending to stay.

Nawan is a rising young musician with $K$ die-hard fans. The $i$ -th fan lives in city $D_i$ . Surprisingly, no fan lives in a city that imposes a quarantine order.

Nawan has just released an album and wants to hold concerts for his fans. Over the objections of his team, Nawan insists that the concerts be held live and in person. He believes a virtual concert cannot convey his musical feeling.

After weighing the budget and resources, Nawan and his team agree to hold at most $P$ concerts. Concerts can be held only in cities without a quarantine order. Nawan has contacted all fans, and each fan agrees to attend exactly one concert. The only remaining question is which cities should host the concerts. Each fan goes to the venue that is closest in travel time. Venues have no capacity limit.

Nawan wants to hold the concerts in at most $P$ cities so that the longest travel time of any fan is as small as possible. You only need to output that minimum longest travel time.

Input

The first line contains four integers $N$ , $M$ , $K$ , $P$ ( $1 \le M < N \le 200000$ , $1 \le K, P \le N - M$ ). These are the number of cities, the number of cities with a quarantine order, the number of fans, and the maximum number of concerts. Each of the next $M$ lines contains $C_i$ and $T_i$ ( $1 \le C_i \le N$ , $1 \le T_i \le 200000$ ). All $C_i$ are distinct. The last line contains $K$ integers $D_i$ ( $1 \le D_i \le N$ ), the city of each fan. No fan lives in a quarantine city, and all fans live in different cities.

Output

Output one integer on a line: the minimum longest travel time needed by any fan to reach a concert venue.

Examples3

Example 1
Input
```
10 4 3 2
1 2
4 4
6 2
7 5
2 5 8
```
Expected output
```
4
```
Example 2
Input
```
8 1 3 5
1 5
4 2 7
```
Expected output
```
0
```
Example 3
Input
```
5 2 2 1
1 14
2 14
3 5
```
Expected output
```
1
```