A binary tree of checkpoint scores 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.
A route is a non-empty sequence of nodes such that consecutive nodes in the sequence are connected by a parent-child edge, no node repeats, and the route may bend at most once (i.e. it may go up from a start node to some node and then down into a different branch, but never up-down-up again) — equivalently, a route is any connected subtree path between two nodes (possibly the same node), not necessarily passing through the root.
Print the maximum possible sum of the node values along any route.
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 maximum route sum.
Constraints
- 1 <= number of nodes <= 400
- Each node value is an integer with -1000 <= value <= 1000