Maximum Path Sum

Problem statement

A trail network is a binary tree whose stations have signed rewards. A visitor may start and finish at any stations but must follow one simple connected route. The planner wants the greatest total reward available on such a route. Your task Find the maximum sum of node values on any nonempty simple path in the binary tree. A path may go upward and then downward through an ancestor, but it cannot revisit nodes or branch into three directions. Important details The path does not have to include the root or end at leaves. With all-negative values, choose the best single node rather than an empty path. Include every station value along the chosen route. Worked example For root -5 with leaf children 4 and 8, the path 4 -> -5 -> 8 totals 7, while the single node 8 totals 8. The maximum is therefore 8.

Input format

The first line contains n. The next n lines contain value left right for nodes 0 through n-1. Child indices are -1 when absent. Node 0 is the root when n > 0. The records form one valid binary tree; n = 0 represents an empty tree.

Output format

Print the maximum path sum.

Constraints

1 <= n <= 2000; -1000 <= value <= 1000. Child indices are -1 or valid node indices; no cycles or shared children.

Sample input

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

Sample output

8