问题 1632 --采花生

1632: 采花生★★

时间限制: 1 Sec  内存限制: 128 MB
提交: 103  解决: 73
[提交][状态][命题人:]

题目描述

在参加“采花生”这个项目比赛时,考官会出示一块 n 行、m 列的花生田, 上面一共种了 n*m 株花生苗。每株花生植株下都结了一定数量的花生果,比赛 开始时选手站在第 1 行,第 1 列的位置,现要求用最短的时间找到结花生果最 多的一株花生植株(数据保证花生果最多的植株只有一株),然后按先向南(下) 走,再向东(右)的路线顺序去采摘它的花生果,沿路经过的其他花生植株下面 的花生果也要一并采摘下来, 但不允许采摘没有路过的花生植株,否则依犯规 出局处理。问这个选手一共可以采摘到多少粒花生果? 

如一块 n=5,m=6 的花生田.

可以发现结花生果最多的那株花生植株在(4,5),则选手采摘的顺序应为 (1,1)-(2,1)-(3,1)-(4,1)-(4,2)-(4,3)-(4,4)-(4,5), 一共采得的花生果粒数为 5+9+10+4+6+9+18+25=86。 

输入

第 1 行有两个整数 n 和 m( 1 < n,m <= 100 ),表示花生田一共有 n 行 m 列。第 2 至 n+1 行,每行有 m 个用空格隔开的整数,第 i + 1 行的第 j 个整 数 Pij(0 <= Pij <= 700)表示花生田里植株 (i, j) 下花生的数目, 0 表示该植株 下没有花生。 


输出

只有一行,一个整数,表示选手一共摘到的花生果数目。


样例输入
Copy
5 6
5 7 4 5 1 13
9 6 3 2 8 7
10 14 0 1 9 4
4 6 9 18 25 0
3 1 2 9 0 2
样例输出
Copy
86

提示

来源

 

[提交][状态]