1066 - [Data Structure] Tree

#	Problem	Pass Rate (passed user / total user)
11208	MaxPath

11208 - MaxPath

Status | Limits Submit

	Time	Memory
Case 1	1 sec	32 MB
Case 2	1 sec	32 MB
Case 3	1 sec	32 MB
Case 4	1 sec	32 MB

Description

Input a complete binary tree where each node has an non-negative weight value w, which is called node weight. Path weight is defined as the summation of node weights in a root-to-leaf path. Please calculate the maximum path weight in the tree.

Input

There are lots of complete binary trees in the input. Each tree occupies a line. Tree height is smaller than 10.

Output

For each tree, output the maximum path weight in a line.

Sample Input Download

16 86 88 38 68 86 43 
65 34 56 88 95 76 76 
5 58 74 39 27 28 2 
12 77 81 92 71 29 45 
3 37 6 69 2 99 60 
97 61 40 50 74 96 35 
8 66 52 61 42 59 19 
78 62 82 86 68 47 81 
8 41 4 67 65 55 26 
53 46 95 24 2 22 94

Sample Output Download

1066 - [Data Structure] Tree Scoreboard

Time

Clarification