1835: 方格取数

Memory Limit：128 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：22 Solved：8

Description

在n*n的方格阵中，从左上角出发，每次只能往正下方或右边走，找出一种路线方案，使得所经历方格中数字和最大，输出这个值。
（下图n=5)
0 5 37 53 9
55 10 19 23 8
65 58 82 89 9
8 0 14 50 68
89 5 10 41 0


Input

第1行：一个整数n   (1<=n<=1000)
第2-n+1行：每行n个非负整数 （整型范围）

Output

一行：一个整数。

Sample Input Copy 

5
0	5	37	53	9
55	10	19	23	8
65	58	82	89	9
8	0	14	50	68
89	5	10	41	0

Sample Output Copy 

467

Source/Category