时空限制

2S/512M

题目描述

apiadu 种了一棵有 $n$ 个节点的树，树的根节点的编号为 $1$，第 $i$ 条边连接了编号为 $u_i$ 和 $v_i$ 的节点。

每到秋天，线段树上编号为 $i$ 的节点会长出 $a_i$ 个果子。apiadu 非常喜欢吃果子，所以他会从线段树上采下 $k$ 个果子来吃。

若定义一个节点的高度为它到根节点的简单路径所经过的点的个数，那么 apiadu 采集所花费的体力为他采集的果子所在节点的最大高度。

但在 apiadu 爬树的过程中，他发现编号为 $b_1, b_2 \dots b_m$ 的节点结的果子发生了变异，如果同时吃下这些变异的果子和一个与它相邻的节点结的果子，会食物中毒，所以它不会同时采集一个变异的果子和一个与它相邻的节点结的果子。

apiadu 想知道，为了能采集 $k$ 个果子，他最少要花费多少体力？如果他无法采集 $k$ 个果子则输出 $−1$。

格式

输入格式

第一行包含三个正整数 $n, m, k$，表示树的结点数量，变异果子数量和想吃的果子数量。

第 $1+x(1 \le x < n)$ 行包含两个正整数 $u_i, v_i$，表示树的边。

第 $n+1$ 行包含 $n$ 个正整数 $a_1, a_2, \dots, a_n$，表示结点上的果子数量。

第 $n+2$ 行包含 $m$ 个正整数 $b_1, b_2, \dots, b_m$，表示变异结点的编号。

输出格式

输出一行一个整数，表示答案。

样例

样例输入 #1

5 1 10
1 2
1 3
2 4
2 5
3 4 5 2 6
2

样例输出 #1

3

数据范围

对于 $100\%$ 的数据，$1 \le m \le n \le 5 \times 10^5, 1 \le k \le 10^{15}$，$1 \le a_i \le 10^9$， $1 \le b_i \le n$，且 $b_i$ 按照升序排序。