题目描述

给定一个数塔，要求从底层走到顶层，每一步只能走到相邻的结点，求经过的结点数字之和的最大值。

输入格式

第一行输入一个整数 $N$，表示数塔的高度。

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

输出格式

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

样例

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

30

数据范围

• $1 \le N \le 100$