Demux Problems Submissions Users Contests Log in Sign up


Max Sum


Submit solution

Points: 100
Time limit: 2.0s
Memory limit: 128M

Author:
Problem type
Allowed languages
C, C++, Java, Python

You are given a binary trees \(T\) with \(N\) nodes.

A path is defined as sequence of nodes such that each pair of adjacent node is connected by an edge.

Output the Path with maximum sum of values of nodes on that path.

Input

First line contains single integer: \(N\).

Following lines of input describe the \(T\).

First line contains single integer : \(root\)

Next line contains \(N\) integers, where \(i^{th}\) integer is the value of the node with index \(i\).

Next \(N\) lines contains two integers each, index of left child and right child of node with index \(i\). If any of integer is \(-1\) then corresponding child is absent.

Output

Ouput Maximum sum.

Constraints

\(1\) \(\leq\) \(N\) \(\leq\) \(10^5\)

Example

Input

3
1
1 2 3
2 3
-1 -1
-1 -1

Output

6

Consider path 2 -> 1 -> 3. Sum \( = 2 + 1 + 3 = 6\).

Note

You can use this template to submit the solution.


Comments

There are no comments at the moment.