题目描述

游戏地图由一个数字三角塔组成。霸王龙从塔顶出发，每走一层，只能进入当前数字左下方或右下方的数字。

经过一个位置时会获得该位置写着的分数。请计算从塔顶走到底层能够获得的最大总分。

输入格式

第一行包含一个整数 $r$，表示三角塔的行数。

接下来 $r$ 行，第 $i$ 行输入 $i$ 个整数。

输出格式

输出能够获得的最大总分。

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

30

数据范围与提示

• $1\le r\le 1000$
• 每个数字在 $0$ 到 $100$ 之间