Problem Description

In a country, there are $n$ cities (numbered from $0$ to $n-1$). These cities are connected by $n$ bidirectional roads (numbered from $0$ to $n-1$), where the road numbered $i$ connects city $i$ to city $r_i$ (a road can connect a city to itself), with a length of $d_i$. Among the $n$ cities, $m$ have their own castles, capable of defending against enemy invasions. If a city without a castle is attacked, the nearest castle will dispatch troops to rescue it.

Your task is to build castles in no more than $k$ cities without castles, such that the maximum distance to the nearest castle for all cities is minimized. In other words, if $dist(c)$ represents the distance from city $c$ to its nearest castle, your task is to minimize $\max\{dist(c)\}$.

The input data guarantees that there is a solution ensuring that every city can be reached by at least one castle.

Input Format

The first line contains three positive integers $n, m, k$. The second line contains $n$ integers $r_0, r_1, \ldots, r_{n-1}$. The third line contains $n$ integers $d_0, d_1, \ldots, d_{n-1}$. The fourth line contains $m$ distinct integers between $0$ and $n-1$, representing the city numbers where the castles are located.

Output Format

Output a single line containing one integer, which is the minimum value of $\max\{dist(c)\}$.

Sample Input and Output

Sample Input #1

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

Sample Output #1

2

Sample Input #2

3 1 1
1 2 0
1 2 3
2

Sample Output #2

1

Sample Input #3

2 1 1
0 1
1 1
1

Sample Output #3

0

Sample Input #4

10 3 3
0 2 0 0 2 2 8 3 8 7
10 9 1 8 1 3 7 2 8 1
3 4 6

Sample Output #4

3

Sample Input #5

2 0 1
1 0
5 10

Sample Output #5

5

Notes

$100\%$ of the data satisfies: $1 \leq d_i \leq 10^5$, $0 \leq m \leq n-k$.

• Subtask 1: $2 \leq n \leq 3000$.
• Subtask 2: $2 \leq n \leq 10^5$.

见题面 Input 部分

见题面 Output 部分