捡水果
说明
徐老师在玩一款游戏，他在一个山顶，现在他要下山，山上有许多水果，徐老师每下一个高度就可以捡起一个水果，并且获得水果的能量。山的形状如图所示：```
3
1 2
6 2 3
3 5 4 1
```
这是一个高度为 $4$ 的山，数字代表水果的能量。每次下一个高度，徐老师需要选择是往左下走，还是往右下走。例如：对于上图的情况，徐老师能获得的最大能量为，$3 + 1 + 6 + 5 = 15$。现在，徐老师希望你能帮他计算出下山能获得的最大能量。
输入格式
第一行输入一个 $n$，代表山的高度。（$1 <; n \leq 1000$）接下来 $n$ 行，第 $i+1$ 行有 $i$ 个数字，代表水果的能量，水果能量为正整数且不大于 $1000$。
输出格式
输出一个数字，代表下山一共获得的最大能量，占一行。样例
4
3
1 2
6 2 3
3 5 4 115相关
在下列比赛中: