题目描述

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

输出格式

输出最长滑雪道的长度。

输入/输出例子1

4
30
35 18
15 27 19
23 22 82 38

3