I have a tree

题目描述

左树 右树 傻傻分不清楚

嘿，大家一起来~

小赌 豪赌 想AC就别怕苦

所以王木木去豪赌了，游戏规则如下：

在这样一棵奇怪的树中，每次王木木把一棵弹珠放在最上面的根上，然后让弹珠自由落体，弹珠有可能往左走，也有可能往右走，每次经过一个点，得分加上这个点的价值，那么王木木最多能得多少分呢？

输入

多组数据输入

每组数据第一行为正整数n(0<n<1000)，为树的深度

接下来n行，第i行有i个正整数(在int范围内)，表示这个点的价值

输出

对于每组数据，输出一行，最大得分的值

输入样例

4
1
3 2
4 10 1
4 3 2 15

输出样例

19

样例解释

                     1
                3         2
           4        10         1
      4         3         2        15
最优路径：1->2->1->15

得分：1+2+1+15 = 19