题目描述

给定一个由 $n$ 行数字组成的数字三角形。请从三角形顶部出发，每一步只能走到下一行中相邻的两个位置之一，也就是从第 $i$ 行第 $j$ 个数可以走到第 $i+1$ 行第 $j$ 个数或第 $i+1$ 行第 $j+1$ 个数。

请计算从顶端走到底端时，路径上经过数字之和的最大值。

例如，当 $n=5$ 时：

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

最大路径为：

7 -> 3 -> 8 -> 7 -> 5

最大和为 $30$。

输入格式

第一行输入一个整数 $n$，表示数字三角形的行数。

接下来 $n$ 行，第 $i$ 行有 $i$ 个整数，表示数字三角形中的数字。

输出格式

输出一个整数，表示从顶端走到底端可以得到的最大路径和。

输入输出样例

输入

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

输出

30

数据范围与提示

对于全部数据，$1 \le n \le 100$，三角形中的每个数字均在 $0$ 到 $99$ 之间。

可以使用动态规划。令 $dp[i][j]$ 表示从位置 $(i,j)$ 出发走到底端能得到的最大和，则：

dp[i][j] = a[i][j] + max(dp[i+1][j], dp[i+1][j+1])

也可以自顶向下递推，维护到达每个位置时的最大路径和。