Mirko 厌倦了他那家著名跨国软件公司 CEO 的高压工作。凭借数百万美元的黄金降落伞（离职补偿金），他决定过上简单的生活，并搬到了 Gorski Kotar。然而，他刚搬去的那个偏远村庄的冬天非常寒冷。他的邻居中没有一个人是在二战后出生的，因此他注定要自己劈柴。

今天，他准备劈他的第一根树干。在劈柴之前，他将树干标记为若干个小到可以放进壁炉的部分，并测量了它们的硬度。Mirko 是一名程序员，因此他注意到这些部分以及它们之间的连接构成了一棵树。

砍断树干上的一个连接（边）对他的斧头造成的伤害，等于砍断该连接后形成的两个连通块中最大硬度之和。

Mirko 只有一把斧头，因此他希望总伤害尽可能小。他想知道，如果他将整根树干砍成可以放进壁炉的单个部分（即砍断所有连接），斧头受到的最小总伤害是多少。

输入格式

第一行包含一个整数 $n$，表示树干部分的数量。这些部分用 $1$ 到 $n$ 的整数标记。

第二行包含 $n$ 个整数 $t_i$（$1 \le t_i \le 10^9$）。其中 $t_i$ 表示标记为 $i$ 的部分的硬度。

接下来的 $n - 1$ 行，每行包含两个整数 $x$ 和 $y$（$1 \le x, y \le n$），表示直接相连的两个部分的编号。

输出格式

输出进行 $n - 1$ 次砍伐后的最小总伤害。

子任务

对于所有子任务，均满足 $1 \le n \le 100\,000$。

样例

输入样例 1

3
1 2 3
1 2
2 3

输出样例 1

8

输入样例 2

4
2 2 3 2
1 3
3 2
4 3

输出样例 2

15

输入样例 3

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

输出样例 3

26

说明

样例 1 说明

有两种方式可以砍伐这根树干：

• 先砍断连接 $(1, 2)$，造成 $1 + 3 = 4$ 的伤害，然后砍断连接 $(2, 3)$，造成 $2 + 3 = 5$ 的伤害。在这种情况下，总伤害为 $9$。
• 先砍断连接 $(2, 3)$，造成 $2 + 3 = 5$ 的伤害，然后砍断连接 $(1, 2)$，造成 $1 + 2 = 3$ 的伤害。在这种情况下，总伤害为 $(2 + 3) + (1 + 2) = 8$。