Mr. Ham 是合肥最著名的建筑师之一，他受邀参与了中国科学技术大学（USTC）新校区的规划工作。

具体来说，USTC 的校园可以看作一棵树 $T = (V, E)$，包含 $n$ 座建筑和 $n - 1$ 条无向边，建筑 $i$ 具有重要性值 $w_i$。保证 USTC 校园是连通的。

校方希望 Mr. Ham 能将校园划分为若干个区域。我们认为一个划分方案是合法的，当且仅当它满足以下条件：

• 每座建筑恰好属于一个区域。
• 任意区域的导出子图是连通的。

校方将一个区域的权重定义为该区域内所有建筑重要性值中的第二大值；如果该区域仅包含一座建筑，则其权重为 $0$。校方希望 Mr. Ham 能最大化所有区域的权重之和。你能帮 Mr. Ham 得到答案吗？

导出子图：如果一个区域由集合 $S \subseteq V$ 中的建筑组成，那么它的导出子图包含集合 $S$ 中的所有建筑，以及两个端点均在集合 $S$ 中的边。

输入格式

第一行包含一个正整数 $n(1 \le n \le 5 \times 10^5)$，表示建筑的数量。 第二行包含 $n$ 个正整数 $w_i(1 \le w_i \le 10^9)$，表示每座建筑的重要性值。 接下来的 $n - 1$ 行包含 USTC 校园的边，每行一条边。第 $i$ 行包含两个整数 $u_i, v_i(1 \le u_i, v_i \le n, u_i \neq v_i)$，表示一条边 $(u, v)$。保证其构成一棵树。

输出格式

输出一行，包含一个整数，表示所有区域权重之和的最大值。

样例

样例输入 1

8
2 5 4 5 3 1 1 3
1 2
1 3
1 4
2 5
2 6
3 7
4 8

样例输出 1

8