Xor Tree

You are given a tree with $N$ vertices labeled from $1$ to $N$ rooted at $1$. The root is not considered a leaf even if it has just one descendant. Each vertex has an associated cost and a state, the state may be active or inactive. Initially all nodes are considered active.

In one operation you may pick a leaf and switch the state from active to inactive or inactive to active for all vertices along the path from the leaf to the root. Print the maximum achievable sum of active vertices if you are allowed to make this operation as many times as you wish on any leaf.

Input

The first line will contain the integer $N$ ($2 \leq N \leq 200\ 000$). The following $N - 1$ lines will contain two values $a$ and $b$, and each pair ($a$ and $b$) represents an edge in the tree. The last line will contain $N$ integers representing the cost of each vertex starting with $1$ ($-10^9 \leq val_i \leq 10^9$).

Output

Only one integer will be printed, the maximum achievable sum.

Notes

For tests worth 10 points, $2 \leq N \leq 20$.
For tests worth 10 extra points, $2 \leq N \leq 1\ 000$.

Example

stdin

5
1 2
1 3
2 4
2 5
1 2 4 -4 -5

stdout

7

Explanation

In the sample we may pick vertex $4$ to apply the operation first, so the vertices on the path $4 \rightarrow 2 \rightarrow 1$ will be flipped from activated to deactivated.

We must also pick vertex $5$ to flip $5 \rightarrow 2 \rightarrow 1$, so in the end $2$ and $1$ will keep being activated but $4$ and $5$ are deactivated. Lastly only vertices $1$, $2$ and $3$ are active so their sum is $7$.