题目描述

小珅同学在玩一款游戏，他在一个山顶，现在他要下山，山上有许多水果，小珅同学每下一个高度就可以捡起一个水果，并且获得水果的能量。山的形状如图所示：

3

1 2

6 2 3

3 5 4 1

这是一个高度为 4 的山，数字代表水果的能量。每次下一个高度，小珅同学需要选择是往左下走，还是往右下走。例如：对于上图的情况，小珅同学能获得的最大能量为，3+1+6+5=15。现在，小珅同学希望你能帮他计算出下山能获得的最大能量。

输入格式

第一行输入一个 n，代表山的高度。（1<n≤1000）

接下来 n 行，第 i+1 行有 i 个数字，代表水果的能量，水果能量为正整数且不大于 1000。

输出格式

输出一个数字，代表下山一共获得的最大能量，占一行。

输入样例 #1

4
3
1 2
6 2 3
3 5 4 1

输出样例 #1

15

输入样例 #2

2
414
699 997

输出样例 #2

1411

输入样例 #3

3
757
840 890
46 763 864

输出样例 #3

2511

数据范围

（1<n≤1000

接下来 n 行，第 i+1 行有 i 个数字，代表水果的能量，水果能量为正整数且不大于 1000。