这道题在某些国家可能家喻户晓，但如果没人提出，其他国家又该如何了解这类问题呢？

Little Cyan Fish (Xiao Qingyu) 和 Huge Nucleus Kernel (Da Heren) 是两位形影不离的好友。2020 年，在备战全国信息学奥林匹克竞赛的训练中，Little Cyan Fish 致力于解决一道来自 2010 年波兰算法竞赛（Potyczki Algorytmiczne 2010）的迷人题目。

两只白蚁正在啃食一排旧木栅栏。栅栏由高度可能各不相同的木板组成。白蚁已经吃掉了一些木板，它们觉得应该让这顿美餐变得更有趣。于是它们决定玩一个游戏，轮流吃掉剩下的木板，每次吃一块。在每一轮中，白蚁只能选择吃掉与已经吃掉的木板相邻的木板。 假设每只白蚁在选择木板时，都力求使自己在整个游戏过程中吃掉的木板高度之和尽可能大，请计算每只白蚁最终吃掉的木板总高度。 题目作者：Tomasz Idziaszek。

这道题引起了 Little Cyan Fish 的浓厚兴趣，给他留下了深刻的印象。多年后，当 Huge Nucleus Kernel 需要为一场比赛准备题目时，他与 Little Cyan Fish 分享了这道题。Little Cyan Fish 感到非常惊讶，因为它让他想起了那道引人入胜的题目。为了激励更多人尝试并解决这个有趣的问题，Little Cyan Fish 和 Huge Nucleus Kernel 决定将其纳入 Universal Cup 比赛中。

Little A 和 Little B 正在进行一场游戏。他们面对的是一个有根树森林，其中每个顶点 $u$ 都带有一个正整数值 $A_u$。

Little A 和 Little B 轮流进行游戏，由 Little A 先手。当前玩家必须选择恰好一个树根进行消除，从而获得该节点的值。被消除节点的子树形成一棵新的有根树，而被消除节点的子节点成为新的树根。

当所有顶点都被消除时，游戏结束。玩家的得分是他们所消除的顶点值之和。

两位玩家都旨在通过最佳策略来优化自己的得分。请确定 Little A 的最终得分。

初始场景提供了一棵具有 $n$ 个顶点的树。顶点编号从 $1$ 到 $n$，其中顶点 $1$ 为根。

输入格式

第一行包含一个整数 $n$ ($2 \le n \le 10^5$)，表示树的大小。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$)，其中 $a_i$ 表示顶点 $i$ 的值。

接下来的 $(n - 1)$ 行中，第 $i$ 行包含两个整数 $u_i$ 和 $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$)，表示连接顶点 $u_i$ 和 $v_i$ 的边。

输出格式

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

样例

输入 1

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

输出 1

7