We are given a tree $T=(V, E)$ with $N$ nodes. Each node in this tree has an integer written on it. Note that these integers can be negative. We want to find two subgraphs of $T$, $T_a=(V_a, E_a)$ and $T_b=(V_b, E_b)$, that satisfy the following conditions:

• $V_a \neq \emptyset, V_b \neq \emptyset$
• $T_a$ and $T_b$ are each connected graphs.
• $V_a \cap V_b = \emptyset$
• Furthermore, there is no edge in $E$ that connects a node in $V_a$ to a node in $V_b$.
• Finally, the sum of the integers written on the nodes in $V_a$ plus the sum of the integers written on the nodes in $V_b$ must be maximized.

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

The numbers above the nodes are the node indices, and the numbers inside the nodes are the values written on them. While there may be multiple ways to choose $T_a$ and $T_b$ satisfying the conditions, if we choose $V_a = \{0, 2, 3\}$ and $V_b = \{5, 6\}$, the sum of the numbers in the two graphs is $\{3 + (-1) + 4\} + \{5 + 3\} = 14$, which is the maximum. Other methods 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. The input is passed as arguments, and the return value of this function is the answer to the problem. $N$ indicates the number of nodes. The nodes are numbered from $0$ to $N-1$. When the variable $i$ is between $0$ and $N-1$ inclusive, the number written on the node with index $i$ is $C[i]$. Also, when the variable $i$ is between $0$ and $N-2$ inclusive, the node with index $Node1[i]$ and the node with index $Node2[i]$ are connected by an edge.

Implementation Details

You must submit exactly one file named tree.cpp. This file must implement the following function:

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

This function must behave as described above. You may create other functions to use internally. The submitted code must not perform input/output operations or access other files.

Constraints

• $-10^9 \leq C_i \leq 10^9$
• $3 \leq N \leq 500,000$

Subtasks

• Subtask 1 [7 points]: $N \leq 20$
• Subtask 2 [19 points]: $N \leq 5000$
• Subtask 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