A mining region is modeled as a binary tree; each node has an integer ore yield, which may be negative (a node can cost more to clear than it returns). For any node, the block yield is the sum of ore yields of that node and all of its descendants (its subtree). Report the maximum block yield over all nodes.
Input format
Line 1: an integer k, the number of tokens on line 2.
Line 2: k space-separated tokens giving the tree in level order. The first token is the root; each subsequent token is an integer yield or null for a missing child. Children of null nodes are omitted.
Output format
A single integer: the maximum block yield.
Constraints
- The tree has between 1 and 2000 nodes (the root is always present).
- Each ore yield is between -1000000 and 1000000.