Problem 2597 --方格取数1

2597: 方格取数1

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 354  Solved: 194
[Submit][Status][Web Board][Creator:][下载FPS1元][添加到购物车][下载测试数据1元][2260kb]

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

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

467

HINT

Source

[Submit][Status]