Binary Casino 是一栋非常特殊的摩天大楼，由 $N$ 个楼层组成，这些楼层通过一个复杂的快速自动扶梯网络连接。

楼层之间的连接设计满足：如果存在一部从楼层 $A$ 到楼层 $B$ 的自动扶梯，那么也存在另一部从楼层 $B$ 到楼层 $A$ 的自动扶梯。此外，对于任意两个楼层 $A$ 和 $B$，从楼层 $A$ 到楼层 $B$ 恰好只有一种方式。

您的经理决定组织一场促销游戏以吸引更多顾客。游戏规则如下：

• 游戏进行一轮或多轮。
• 在每一轮中，顾客可以选择一个楼层 $S$ 作为该轮的起点。此时，他会获得与楼层 $S$ 相关联的固定数量的代币 $t(S)$。然后，他可以利用自动扶梯移动到其他楼层。
• 如果顾客决定乘坐自动扶梯从楼层 $A$ 到楼层 $B$，且当前拥有 $X$ 个代币，则他必须支付 $X - (X \text{ AND } t(B))$ 个代币才能进入楼层 $B$，其中 “AND” 是按位与运算符，“$-$” 是标准的减法运算符，$t(B)$ 是与楼层 $B$ 相关联的代币数量。
• 顾客可以决定在任意楼层（包括 $S$）结束该轮，并保留该轮获得的代币。然后，如果可行，他可以从任意楼层开始新的一轮。
• 任意两轮游戏不能具有相同的起点和终点楼层对，即使方向相反也不行。也就是说，交换起点和终点楼层后仍被视为相同的楼层对。

您的经理很好奇顾客在游戏中最多可以获得多少代币。

输入格式

输入的第一行包含一个整数 $N$ ($1 \le N \le 3 \cdot 10^5$)，表示赌场摩天大楼的楼层数。

第二行包含 $N$ 个整数 $V_i$ ($0 \le V_i < 2^{20}$)。第 $i$ 个整数 $V_i$ 表示顾客在第 $i$ 个楼层上获得的代币数量。

接下来的 $N - 1$ 行，每行包含两个整数 $A$ 和 $B$ ($0 \le A, B < N$)，描述楼层 $A$ 和 $B$ 之间的自动扶梯连接。

输出格式

输出一个整数，表示顾客最多可以获得的代币数量。

样例

输入样例 1

4
1 2 2 1
0 1
1 2
2 3

输出样例 1

8

输入样例 2

5
7 3 5 6 7
0 1
1 2
2 3
2 4

输出样例 2

48