[SCOI2008] 城堡 - 数据加强版

题目背景

[原题弱化版](https://www.luogu.com.cn/problem/P2538)

题目描述

在一个国家里,有 $n$ 个城市(编号为 $0$ 到 $n-1$)。这些城市之间有 $n$ 条双向道路相连(编号为 $0$ 到 $n-1$),其中编号为 $i$ 的道路连接了城市 $i$ 和城市 $r_i$(一条道路可以连接一个城市和它自身),长度为 $d_i$。$n$ 个城市中有 $m$ 个拥有自己城堡,可以抵御敌人侵略。如果没有城堡的城市遭受攻击,则离它最近的城堡将派兵前往救援。 你的任务是在不超过 $k$ 个没有城堡的城市中建立城堡,使得所有城市中“离最近城堡的距离”的最大值尽量小。换句话说,若令 $dist(c)$ 表示城市 $c$ 的最近城堡离它的距离,则你的任务是让 $\max\{dist(c)\}$ 尽量小。 输入数据保证存在方案使得对于每个城市,至少有一个城堡能够到达。

输入输出格式

输入格式


输入第一行为三个正整数 $n, m, k$。第二行包含 $n$ 个整数 $r_0,r_1,\ldots,r_{n-1}$。第三行包含 $n$ 个整数 $d_0,d_1,\ldots,d_{n-1}$。第四行包含 $m$ 个各不相同的 $0$ 到 $n-1$ 之间的整数,分别为 $m$ 个城堡所在的城市编号。

输出格式


输出仅一行,包含一个整数,即 $\max\{dist(c)\}$ 的最小值。

输入输出样例

输入样例 #1

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

输出样例 #1

2

输入样例 #2

3 1 1
1 2 0
1 2 3
2

输出样例 #2

1

输入样例 #3

2 1 1  
0 1  
1 1  
1

输出样例 #3

0

输入样例 #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

输出样例 #4

3

输入样例 #5

2 0 1
1 0
5 10

输出样例 #5

5

说明

$100\%$ 的数据满足:$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$。