AT_wupc2012_4.三角パズル

在你忙碌的过程中，压缩文件的解压似乎已经完成了。你打开一看，发现了一个包含按直角三角形排列的数列的文本文件。

例如：

7
2 3
1 5 4

看起来，这是一个从最上方的顶点出发，每次只能选择往下一层的正下方或右下方的数字，直到底边为止，要求出路径上数字之和的最大值的问题。这很简单。在上面的例子中，选择 $7 \to 3 \to 5$ 是最优的，合计为 $15$。

不过，这样的文件有很多，有的甚至有 100 层的数据。看来，只有解出这个问题才能获得参赛资格……？不对，这其实是一个编程竞赛的邀请函。只要写一个程序，输入数列后能求出最大值就行了。大概邀请你的人也是这么想的。

给定如下按直角三角形排列的数列。从顶点出发，每次只能选择下一层的正下方或右下方的数字，直到底边为止。请计算路径上数字之和的最大值。

例如，给定如下数列：

3
7 4
2 4 6
8 5 9 3

如果正确选择路径，则为：

3
7 4
2 4 6
8 5 9 3

合计为 $3 + 7 + 4 + 9 = 23$。

输入以如下格式从标准输入给出。

$N$
$a_{1,1}$
$a_{2,1}\ a_{2,2}$
$a_{3,1}\ a_{3,2}\ a_{3,3}$
$\cdots$
$a_{i,1}\ a_{i,2}\ \cdots\ a_{i,i}$
$\cdots$
$a_{N,1}\ a_{N,2}\ \cdots\ a_{N,N}$

• 第 $1$ 行给出直角三角形的高度 $N$（$1 \leq N \leq 100$）。
• 第 $i$ 行（$2 \leq i \leq N+1$）有 $i-1$ 个用半角空格分隔的整数。
• 数列中的数字满足 $0 \leq a_{i,j} \leq 100$（$1 \leq j \leq i \leq N$）。

请输出路径上数字之和的最大值，输出为一行。

在 100 分中，有 50 分的数据满足 $N \leq 20$。

输出一行，表示路径上数字之和的最大值。

无。

由 ChatGPT 4.1 翻译