Problem1701--数字三角形

1701: 数字三角形

Time Limit: 1.000 Sec  Memory Limit: 128 MB
Submit: 299  Solved: 150
[Submit] [Status] [Web Board] [Creator:]

Description

数字三角形,从三角形顶部往下走,只能往左下或右下走,求走到最下面时所经过的数字和最大为多少?(下图为n=6时的情况)







2








96
30






83
52
60




21
65
44
61


8
79
50
41
21
61
41
50
38
79
10


Input

第1行:整数n(1<=n<=1000)

第2-n+1行:每行若干整数,第i行有i-1个整数空格分隔。


Output

一行:一个整数,表示所经过数字的最大和。

Sample Input

6					
2					
96	30				
83	52	60			
21	65	44	61		
8	79	50	41	21	
61	41	50	38	79	10

Sample Output

375

Source/Category


[Submit] [Status]