g6-07884. 数字三角形 未做

一个 $n$ 层的数字三角形，第 $i$ 层有 $i$ 个整数。从顶部出发，每次可以走到下一层的正下方或右下方，求走到底部的最大路径和。

第一行一个整数 $n$。

接下来 $n$ 行，第 $i$ 行有 $i$ 个整数。

一行一个整数，表示最大路径和。

输入 1

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

输出 1

30

$1\le n\le 1000$，$-10000\le$ 数字 $\le 10000$。