题目描述

给定一个数塔，要求从底层走到顶层（注：也可理解为从顶层到底层，逻辑等价），每一步只能走到相邻的结点，求经过的结点数字之和的最大值。

输入格式

第一行输入一个整数 $N$（$1 \le N \le 100$），表示数塔的高度。

接下来 $N$ 行，第 $i$ 行包含 $i$ 个整数（所有整数均在 $[0, 99]$ 范围内），依次表示数塔第 $i$ 层的数字。

输出格式

输出一个整数，表示从底层走到顶层经过的数字的最大和。

输入输出样例 #1

样例

输入

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

输出

30