不，我们并不想要小组作业。在小组作业里，$1+1 < 1$ 这种事都可能发生。然而，你现在是一个三人小组的组长。幸运的是，由于你是尊贵的组长，你的组员会为你写下所有东西。不幸的是，你必须把新的算法作业分配给你的两名组员——Dian 先生和 Beng 先生，他们无法正确理解对方的想法，并在合作中把所有细节都搞砸了。

新的作业是关于一棵树的：树上有 $n$ 个顶点，由 $n-1$ 条双向边连接。每个顶点 $i$ 都是一个分值为 $a_i$ 的问题。你可以为每位成员分配一条树上的路径，然后 Dian 先生和 Beng 先生将独立解决他们路径上的问题。作业的最终得分由恰好被一名成员访问过的顶点的分值之和决定——正如我们之前提到的，如果他们两人都独立解决了同一个问题，他们会因为争论谁是对的而浪费大量精力，所有的努力都将付诸东流。

现在，你——Ji 先生——想要最大化最终得分（以及不因 GPA 太低而被学校开除的机会）。做出明智的选择吧！

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 2 \times 10^5$)，表示顶点的数量。

第二行包含 $n$ 个用空格分隔的整数，第 $i$ 个整数表示 $a_i$ ($1 \le a_i \le 10^4$)。

接下来的 $n-1$ 行，每行包含两个整数 $u, v$ ($1 \le u, v \le n$)，表示 $(u, v)$ 是一条树边。

保证输入的边构成一棵 $n$ 个顶点的树。

输出格式

在一行中输出一个整数，表示最优分配路径下的最大得分。

样例

样例输入 1

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

样例输出 1

36

样例输入 2

1
1

样例输出 2

0

样例输入 3

3
1 2 3
1 2
2 3

样例输出 3

6

说明

样例 1 的一个最优解是路径 $(2, 3)$ 和 $(4, 5)$。这两条路径在 $1$ 处相交，我们可以得到其余所有顶点的分值。

注意，你必须为你的组员分配恰好两条路径。因此，对于样例 2，你只能给 Dian 先生和 Beng 先生分配 $(1, 1)$ 和 $(1, 1)$，这会导致得分为 $0$。