1568: 数塔

Memory Limit：128 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：51 Solved：34

Description

   有形如下图所示的数塔，寻找一条从顶部到底边的路径，使得路径上所经过的数字之和最大。路径上的每一步都只能往左下或右下走。只需要求出这个最大和即可，不必给出具体路径。

    三角形的行数大于1小于等于100，数字为0 -99。


Input

输入有n+1行：第 1 行是数字三角形的行数 n (1<=n<=100)。接下来 n行是数字三角形各行中的数字。所有数字在0~99 之间。

Output

输出最大路径的值。

Sample Input Copy 

5
13
11 8
12 7 26
6 14 15 8
12 7 13 24 11

Sample Output Copy 

86

HINT

1<=n<=100