题目描述

Michael 喜欢滑雪，这并不奇怪， 因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael 想知道在三角形区域中最长的滑坡。区域的每个数字代表点的高度。下面是一个例子:

         30  
      35    18
   15    27    19
23    22    82    38

一个人可以从上面点滑向左下或右下相邻两个点之一，并且要高度减小。在上面的例子中，一条可滑行的滑坡为30-18。当然35-27-22更长。事实上，这是最长的一条。

输入格式
第一行表示区域的行数 N (1 <=N <= 20)。
下面是 N 行，第 i+1 行有 i 个整数，代表高度 h，0<=h<=10000

输出格式
输出最长滑雪道的长度。

样例

4
30
35 18
15 27 19
23 22 82 38

3