Alice 和 Bob 有一个树(无向非循环连通图)。树的第 i 个顶点有 ai 巧克力等待被拾取。首先,他们选择两个不同的顶点作为起始位置(爱丽丝选择第一个)并取出其中包含的所有巧克力。
然后,他们交替移动,一次选择一个顶点并收集该节点的所有巧克力。为了使事情变得更有趣,他们决定只有当他/她在他/她的上一回合中选择了与该顶点相邻的顶点并且该顶点在其他移动期间尚未被任何人选择时才可以选择一个顶点。
如果任何时候其中一个人无法选择满足所有规则的节点,他/她将跳过他/她的回合,让另一个人尽可能地挑选巧克力。这样一直持续到他们都无法再挑选巧克力为止。
由于他们对巧克力的贪婪,他们想收集尽可能多的巧克力。然而,由于他们是朋友,他们只关心他们一起获得的巧克力总数。他们最多可以挑选多少块巧克力?
输入
输入的第一行包含单个整数 n (2 ≤ n ≤ 100 000) - 树中的顶点数。
第二行包含n个整数ai(1≤ai≤109),其中第i个数字代表节点i处存储的巧克力数量。
然后遵循描述树的 n - 1 行。它们每个都包含两个整数 ui 和 vi (1 ≤ ui, vi ≤ n) - 由第 i 条边连接的顶点索引。
输出
打印如果 Alice 和 Bob 表现最佳,他们可以一起收集的巧克力数量。
示例
输入 #1
9 1 2 3 4 5 6 7 8 9 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9
输出 #1
25
输入 #2
2 20 10 1 2
输出 #2
30
注意
在第一个示例中,Alice 可能从顶点 9 开始,Bob 从顶点 8 开始。Alice 将选择顶点 1,而 Bob 现在没有选择。 Alice 选择了顶点 7,然后他们都停止了。
在第二个示例中,它们都将交替选择其中一个节点。