Description

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

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

It is guaranteed that there exists a plan 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 already have castles.

Output Format

Output a single line containing one integer: the minimum possible 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

Constraints:

$100\%$ of the testdata satisfies $1\leq d_i\leq 10^5$ and $0\leq m\leq n-k$.

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

Translated by ChatGPT 5