A. 二度树上的染色游戏
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

一棵$$$n$$$个节点的二度树（节点最多拥有两个孩子节点的树），编号依次为$$$1 \sim n$$$，其中$$$1$$$为根节点，第$$$i$$$个节点有一个权值$$$w_i$$$。

你在这棵二度树上进行一个回合制游戏，游戏一开始，根节点会被染成红色，其他节点为白色。

对于每一轮，你可以先删掉任何一条边，然后所有与红色节点存在边的节点会被染成红色。

不断进行这样的回合，直到无法染色新的节点为止。游戏的得分是所有白色点的权值总和 - 所有红色点的权值总和。

请计算一下游戏的最高得分是多少？

Input

只含一个样例。

第一行是一个整数$$$n~(1 \le n \le 10000)$$$，表示节点的个数。

第二行是 $$$n$$$ 个整数,表示节点 $$$1\sim n$$$ 的节点权值，所有整数属于 $$$[1,10000]$$$ 区间。

以后的 $$$n-1$$$ 行，每行两个整数$$$u,v~(1 \le u \lt v \le n)$$$，表示$$$v$$$是$$$u$$$的孩子节点。

输入保证输入的树是二度树。

Output

输出一行，为一个整数，表示结果。

Example
Input
6
1 5 4 1 2 3
1 2
1 3
2 4
2 5
3 6
Output
6
Note

第一回删除边$$$(1,2)$$$; 第二回删除边$$$(3,6)$$$。 这样只有节点$$$1,3$$$被染色，红点权值和为$$$5$$$,白点权值和为$$$11$$$，所以游戏得分是$$$6$$$。