Castle Placement Optimization

In a country, there are \(n\) cities (numbered \(0\) to \(n-1\)) connected by \(n\) bidirectional roads (numbered \(0\) to \(n-1\)). The road with index \(i\) connects city \(i\) and city \(r_i\) and has length \(d_i\) (note that a road may even connect a city to itself). Among these cities, \(m\) cities initially have a castle that can repel enemy invasions. If a city without a castle is attacked, the nearest castle will send troops for the rescue.

Your task is to build castles in at most \(k\) additional cities (which currently do not have a castle) so that the maximum distance from any city to its nearest castle, i.e. \(\max\{dist(c)\}\), is minimized. Here, \(dist(c)\) denotes the distance from city \(c\) to the nearest castle.

It is guaranteed that there exists a strategy such that every city is reachable by at least one castle.

inputFormat

The first line contains three integers \(n\), \(m\) and \(k\), where \(n\) is the number of cities, \(m\) is the number of cities that initially have a castle and \(k\) is the maximum number of additional castles you can build.

The second line contains \(m\) distinct integers denoting the indices of the cities that initially have a castle. (If \(m=0\), this line is empty.)

Then follow \(n\) lines, each line contains two integers \(r_i\) and \(d_i\) (for \(i=0,1,\ldots,n-1\)), indicating that there is a bidirectional road connecting city \(i\) and city \(r_i\) with length \(d_i\).

outputFormat

Output a single integer representing the minimized maximum distance from any city to its nearest castle after optimally adding at most \(k\) castles.

sample

5 1 1
2
1 3
2 4
3 5
4 2
0 1

4