题目描述

数字三角形。如下所示为一个数字三角形。请编一个程序计算从顶到底的某处的一条路径，使该路径所经过的数字总和最大。只要求输出总和。

1. 一步可沿左斜线向下或右斜线向下走；
2. 三角形行数小于等于 $100$；
3. 三角形中的数字为 $0,1,\dots,99$。

输入格式

第一行，正整数 $n$，表示数字三角形的行数；

接下来共 $n$ 行，第 $i$ 行（$1\le i\le n$）有 $i$ 个正整数，所有整数介于 $0\sim 99$ 之间。

输出格式

最大的数字和。

样例

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

30

数据范围

$n\le 100$，三角形中的数字为 $0,1,\dots,99$。

来源

CodesOnline