题目描述

观察下面的数字金字塔：

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

请编写程序查找一条从最高点到底部任意位置结束的路径，使路径经过数字的和最大。

每一步可以从当前数字走到左下方的数字，也可以走到右下方的数字。

输入格式

第一行包含一个整数 $R$，表示数字金字塔的行数。

接下来 $R$ 行，每行包含对应行的若干个整数，表示该行的数字。

输出格式

输出一行，包含从顶部到底部任意位置结束的路径中可能得到的最大数字和。

样例

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

86

数据范围

$1 \le R \le 1000$。

所有提供的整数均为非负整数，且不大于 $100$。