Description

在讲述DP算法的时候，一个经典的例子就是数塔问题，它是这样描述的： 有如下所示的数塔，要求从顶层走到底层，若每一步只能走到相邻的结点，则经过的结点的数字之和最大是多少？ 已经告诉你了，这是个DP的题目，你能AC吗?（图见课件上练习题的示图）

Input Format

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

Output Format

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

Sample

【输入样例】

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

【输出样例】

86