There is a tree $T=(V,E)$ with $N$ vertices. An integer is written on each vertex; note that it may be negative. We want to find two subgraphs $T_a=(V_a,E_a)$ and $T_b=(V_b,E_b)$ of $T$ satisfying the following conditions.

• $V_a\ne\varnothing,\quad V_b\ne\varnothing$

• $T_a$ and $T_b$ are each connected.

• $V_a\cap V_b=\varnothing$

• There is no edge in $E$ joining a vertex of $V_a$ to a vertex of $V_b$.

• The sum of all integers written on vertices in $V_a$ and all integers written on vertices in $V_b$ must be as large as possible.

Consider the example in the following figure: $T=(\{0,1,2,3,4,5,6\},\{(0,1),(0,2),(2,3),(2,4),(4,6),(5,6)\})$.

The numbers above the vertices are their labels; the numbers inside them are their values. There may be several choices of $T_a,T_b$ satisfying the conditions. Taking $V_a=\{0,2,3\}$ and $V_b=\{5,6\}$ gives a maximum total of $\{3+(-1)+4\}+\{5+3\}=14$. Other choices are possible, but no value greater than $14$ can be obtained.

You must implement the following function.

long long findSum( int N, int C[], int Node1[], int Node2[] );

This function is called exactly once. Input is passed through its arguments, and its return value is the answer. $N$ is the number of vertices, numbered from $0$ to $N-1$. For $0\le i\le N-1$, C[i] is the integer written on vertex $i$. For $0\le i\le N-2$, an edge joins vertices Node1[i] and Node2[i].

Implementation Details

You must submit exactly one file named tree.cpp, implementing the following function.

long long findSum( int N, int C[], int Node1[], int Node2[] );

The function must behave as described above. You may define other functions for internal use. Your submitted code must not perform input/output or access other files.

Sample Grader

The provided grader reads input in the following format.

• Line 1: $N$

• Line 2: $N$ integers $C_0,C_1,\ldots,C_{N-1}$, the vertex values in order.

• The next $N-1$ lines: two integers $a,b$ indicating an edge between vertices $a$ and $b$.

Be careful: if spaces or other characters follow the character representing the last digit on an input line, the grader may not work correctly.

The grader prints the value returned by your findSum() function.

Constraints

• $-10^9\le C_i\le10^9$

• $3\le N\le500,000$

Subtasks

1. (7 points) $N\le20$

2. (19 points) $N\le5000$

3. (74 points) No additional constraints.

Examples

Input 1

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

Output 1

14