A vault network is a binary tree; each vault holds a non-negative integer amount of loot. A silent alarm links every vault to its direct parent, so you may not rob a vault and its immediate parent on the same night. Choose any set of vaults that contains no parent-child pair, and maximize the total loot taken.
Report the maximum total loot.
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 a non-negative integer loot amount or null for a missing child. Children of null nodes are omitted.
Output format
A single integer: the maximum total loot with no parent-child pair chosen.
Constraints
- The tree has between 1 and 2000 nodes (the root is always present).
- Each loot amount is between 0 and 1000000.