CF533A.Berland Miners

The biggest gold mine in Berland consists of n caves, connected by n - 1 transitions. The entrance to the mine leads to the cave number 1, it is possible to go from it to any remaining cave of the mine by moving along the transitions.

The mine is being developed by the InMine Inc., k miners work for it. Each day the corporation sorts miners into caves so that each cave has at most one miner working there.

For each cave we know the height of its ceiling h__i in meters, and for each miner we know his height s__j, also in meters. If a miner's height doesn't exceed the height of the cave ceiling where he is, then he can stand there comfortably, otherwise, he has to stoop and that makes him unhappy.

Unfortunately, miners typically go on strike in Berland, so InMine makes all the possible effort to make miners happy about their work conditions. To ensure that no miner goes on strike, you need make sure that no miner has to stoop at any moment on his way from the entrance to the mine to his cave (in particular, he must be able to stand comfortably in the cave where he works).

To reach this goal, you can choose exactly one cave and increase the height of its ceiling by several meters. However enlarging a cave is an expensive and complex procedure. That's why InMine Inc. asks you either to determine the minimum number of meters you should raise the ceiling of some cave so that it is be possible to sort the miners into the caves and keep all miners happy with their working conditions or to determine that it is impossible to achieve by raising ceiling in exactly one cave.

贝尔兰最大的金矿由 $n$ 个洞穴组成，这些洞穴通过 $n-1$ 条通道相互连接。矿井入口通向编号为 $1$ 的洞穴，从该洞穴出发，可沿通道到达矿井中其余任意一个洞穴。

该矿井由 InMine 公司开发，公司雇有 $k$ 名矿工。每天，公司需将矿工分配至各洞穴工作，使得每个洞穴至多安排一名矿工。

对每个洞穴 $i$，已知其洞顶高度 $h_i$（单位：米）；对每个矿工 $j$，已知其身高 $s_j$（单位：米）。若某矿工的身高不超过其所在洞穴的洞顶高度，则他能舒适地站立；否则，他必须弯腰，从而感到不快。

不幸的是，矿工们在贝尔兰经常举行罢工，因此 InMine 公司竭尽全力改善矿工的工作条件以使其满意。为确保无矿工罢工，必须保证：任一矿工从矿井入口（即洞穴 $1$）前往其被分配的工作洞穴的整条路径上，均无需弯腰（特别地，他必须能在其工作洞穴中舒适站立）。

为达成此目标，你恰好可选择一个洞穴，并将其洞顶高度提升若干米。然而，扩大洞穴是一项昂贵且复杂的工程。因此，InMine 公司要求你：要么确定为使矿工能被合理分配至洞穴且全部满意工作条件，所需提升的洞顶高度的最小值（仅允许提升一个洞穴）；要么判定仅提升一个洞穴的洞顶高度无法实现该目标。

The first line contains integer n (1 ≤ n ≤ 5·105) — the number of caves in the mine.

Then follows a line consisting of n positive integers _h_1, _h_2, ..., h__n (1 ≤ h__i ≤ 109), where h__i is the height of the ceiling in the i-th cave.

Next n - 1 lines contain the descriptions of transitions between the caves. Each line has the form a__i, b__i (1 ≤ a__i, b__i ≤ n, a__i ≠ b__i), where a__i and b__i are the numbers of the caves connected by a path.

The next line contains integer k (1 ≤ k ≤ n).

The last line contains k integers _s_1, _s_2, ..., s__k (1 ≤ s__j ≤ 109), where s__j is the j-th miner's height.

第一行包含一个整数 $n$（$1 \leq n \leq 5\cdot10^5$）—— 矿井中洞穴的数量。

接下来一行包含 $n$ 个正整数 $h_1,\,h_2,\,...,\,h_n$（$1 \leq h_i \leq 10^9$），其中 $h_i$ 表示第 $i$ 个洞穴的洞顶高度。

随后 $n-1$ 行描述洞穴之间的通道。每行形如 $a_i,\,b_i$（$1 \leq a_i,\,b_i \leq n$，且 $a_i \neq b_i$），表示编号为 $a_i$ 和 $b_i$ 的洞穴之间有一条通道。

下一行包含一个整数 $k$（$1 \leq k \leq n$）。

最后一行包含 $k$ 个整数 $s_1,\,s_2,\,...,\,s_k$（$1 \leq s_j \leq 10^9$），其中 $s_j$ 表示第 $j$ 位矿工的身高。

In the single line print the minimum number of meters that you need to raise the ceiling by in some cave so that all miners could be sorted into caves and be happy about the work conditions. If it is impossible to do, print  - 1. If it is initially possible and there's no need to raise any ceiling, print 0.

在单行中输出为使所有矿工都能被分配到洞穴中且对工作条件感到满意，所需提升某洞穴天花板的最小米数。如果无法实现，则输出 -1；如果初始状态已满足条件且无需提升任何天花板，则输出 0。

In the first sample test we should increase ceiling height in the first cave from 5 to 11. After that we can distribute miners as following (first goes index of a miner, then index of a cave): .

In the second sample test there is no need to do anything since it is already possible to distribute miners as following: .

In the third sample test it is impossible.

在第一个样例测试中，我们需要将第一个洞穴的天花板高度从 5 增加到 11。之后，我们可以按如下方式分配矿工（先为矿工编号，再为洞穴编号）：。

在第二个样例测试中，无需进行任何操作，因为此时已可按如下方式分配矿工：。

在第三个样例测试中，这是不可能的。