Description

In a country, there are $n$ cities (numbered $0$ to $n-1$). They are connected by $n$ bidirectional roads (numbered $0$ to $n-1$), where road $i$ connects city $i$ and city $r_i$ (a road may connect a city to itself) and has length $d_i$. Among the $n$ cities, $m$ of them have their own castles and can resist enemy invasions. If a city without a castle is attacked, the nearest castle will send troops to rescue it.

Your task is to build castles in at most $k$ cities that currently do not have castles, so that the maximum among all cities of the distance to the nearest castle is as small as possible. In other words, let $dist(c)$ be the distance from city $c$ to its nearest castle; your task is to minimize $\max\{dist(c)\}$.

The input guarantees that there exists a solution such that for every city, at least one castle can reach it.

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$, which are the indices of the cities that have castles.

Output Format

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

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

2

3 1 1
1 2 0
1 2 3
2

1

2 1 1  
0 1  
1 1  
1 

0

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

3

2 0 1
1 0
5 10

5

Hint

$100\%$ of the testdata satisfies: $2 \leq n \leq 50$, $1 \leq d_i \leq 10^6$, $0 \leq m \leq n - k$.

Translated by ChatGPT 5