Maximum sum on a tree

Given a tree with $n$ vertices, where the vertex numbered $i(1\le i\le n)$ contains $c_i$ coins. Select a subset of vertices such that no two of them are adjacent (i.e., connected by an edge), and the sum of coins in the selected vertices is maximized.

Input

The first line contains the number of vertices $n(1\le n\le 10^5)$ in a tree. Each of the next $n-1$ lines contains two integers $u$ and $v(1\le u,v\le n)$, defining an edge in the tree. The last line contains $n$ non-negative integers $c_1,...c_n$ — the number of coins in each vertex of the tree.

Output

Print the maximum possible sum of coins that can be obtained by selecting a subset of vertices in the tree with no adjacent vertices.

Examples