You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

  在冒险的途中，有一片区域，有 $r$ 个房间，共有 $r-1$ 条道路连接这些房间，且刚开始时任意两个房间都可以相互到达。

  你曾获得一个神器，虽然只能发动一次，但只要发动，就能把当前房间以及所有与当前房间连通的所有房间的宝藏全部挖出。

  聪明的你发现有些房间的宝藏价值 $v_i$ 是负数，因此你决定在发动神器之前，先阻断某些道路，最终获得最大价值的宝藏。

Format

Input

  第一行，一个整数 $r \space (1 \leq r \leq 10^5)$，表示房间的个数

  第二行，$r$ 个整数，表示第 $i$ 个房间的宝藏价值 $v_i$

  接下来 $r-1$ 行，每行两个整数 $x, y$，表示第 $x$ 个房间与第 $y$ 个房间有一条道路

Output

  最大可能获得的宝藏价值之和（保证答案不超过int类型的范围）

Samples

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

3

4
10 -1 -5 7
1 2
2 3
3 4

11

2
-2 -1
1 2

-1

Notes

  至少要选择一个房间作为当前房间