题目描述

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

         7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   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$

来源

POJ1163