A binary tree of relay-station signal strengths is given in level-order form (a single line of space-separated tokens, null marking a missing child; every non-null node contributes exactly two following tokens for its children). The tree always has at least one node.
Define the distance between two nodes as the number of edges on the unique path connecting them (a node's distance to itself is 0). Find the maximum such distance achieved by any pair of nodes in the tree. If several pairs of nodes achieve this maximum distance, consider all paths of that maximum length and print the greatest possible sum of the node values that lie on any one of them.
Input format
Line 1: space-separated level-order tokens describing the binary tree (integers and the token null). The tree has at least 1 node.
Output format
A single integer: the sum of node values along a maximum-distance path, chosen as described above.
Constraints
- 1 <= number of nodes <= 300
- Each node value is an integer with -1000 <= value <= 1000