题目描述

下图显示了一个数字三角形。每一步都可以向左斜下方走或向右斜下方走，计算从顶到底某条路线上经过的数字的最大和。

在上面的样例中，从 7→3→8→7→5 的路径产生了最大权值。

输入格式

第$1$行包含一个整数$n$，表示三角形的行数。下面的$n$行描述了三角形的数据。三角形中的所有整数都为$0$～$9$$9$。

输出格式

输出从顶到底某条路线上经过的数字的最大和。

样例

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

30

数据范围

$1<n≤100$

来源

• IOI1994 Day1T1
• POJ1163