题目描述

在讲述DP算法的时候，一个经典的例子就是数塔问题，它是这样描述的：

有如下所示的数塔，要求从顶层走到底层，若每一步只能走到相邻的结点，则经过的结点的数字之和最大是多少？

已经告诉你了，这是个DP的题目，你能AC吗?（图见课件上练习题的示图）

输入格式

第一行为$\red{n(n<10)}$，表示数塔的层数 从第2行至$\red{n+1}$行，每行有若干个数据，表示数塔中的数值。

输出格式

输出路径和最大的路径值。

样例

输入样例

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

输出样例

86