Castle Placement Optimization

In a country, there are $n$ cities (labeled $0$ to $n-1$). There are $n$ bidirectional roads (labeled $0$ to $n-1$), where the road with index $i$ connects city $i$ and city $r_i$ (a road may connect a city to itself) and has length $d_i$. Out of these $n$ cities, $m$ cities already have their own castles, which can fend off enemy attacks. When a city that does not have a castle is attacked, the nearest castle will send troops for its defense.

You are allowed to build castles in at most $k$ cities that do not already have one. Let $\text{dist}(c)$ be the distance from city $c$ to its nearest castle. Your task is to choose where to build the additional castles so that the value $\max_{0\le c<n} \text{dist}(c)$ is minimized.

The input guarantees that there exists a way to ensure every city can be reached by at least one castle.

inputFormat

The first line contains three integers: $n$, $m$, and $k$, where

• $n$: the number of cities.
• $m$: the number of cities that already have a castle.
• $k$: the maximum number of additional castles you can build.

The second line contains $m$ distinct integers in the range $[0, n-1]$ representing the indices of the cities that already have a castle. (If $m=0$, this line will be empty.)

Then follow $n$ lines. The $i$-th of these lines (with $i$ from $0$ to $n-1$) contains two integers $r_i$ and $d_i$, indicating that road $i$ connects city $i$ with city $r_i$ and has length $d_i$.

outputFormat

Output a single integer representing the minimized maximum distance, i.e. the smallest possible value of $\max_{0\le c<n} \text{dist}(c)$ after optimally building at most $k$ additional castles.

sample

3 1 1
0
1 5
2 3
0 4

3