Problem1649--VIJOS-P1519

1649: VIJOS-P1519

Time Limit: 0 Sec  Memory Limit: 128 MB
Submit: 0  Solved: 0
[Submit] [Status] [Web Board] [Creator:]

Description

蜗牛小笨(BEN)遇到一个类似这样的迷宫: 1 1  2 2  1  1 这个迷宫是一个等腰直角三角形,每个点上都有一个数字,蜗牛有一次使用魔法的机会。 蜗牛行进的方式: 1、行走:蜗牛进行行走,可以走到下一行、同一列或者下一行、右边一列。 2、魔法:只能使用一次,可以从第x行飞到第(x+1)行的任意一列。 要求:蜗牛所经之路的数字和最大。

Input

第一行是一个数n,代表这个三角形的腰的长度。 第2~(n+1)行中,第m行有(m-1)个数,代表这些数字。 输入数据保证: 0< n< 300 各个数字不超过2*maxlongint

Output

一个数:最大的数字和 输出数据保证不超过2*maxlongint

Sample Input Copy

3
1
1 2
2 1 1

Sample Output Copy

5

HINT

样例解释: 三角形 1   \ 1  \-> 2    (正常行进)         / 2< -/  1          1      (魔法) 所以,答案是1+2+2=5 (看不清请复制到记事本中)