Problem G: 机器人路径5*

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:11 Solved:3

Description

       一个机器人位于一个 m x n 方格的左上角(起始点在下图中标记为“Start”)。机器人每次只能向下或者向右移动一步。机器人试图到达方格的右下角(在下图中标记为“Finish”)。          

       这次小明的机器人又迎来了新的挑战,网格中设置了泥坑。下图中每个单元格包含一个能量值 energy[i][j]。

  • 如果 energy[i][j] >= 0,机器人可以获得该单元格的能量。
  • 如果 energy[i][j] < 0,机器人会遇到一个泥坑,走出这个泥坑机器人将会消耗掉该单元格绝对值的能量。
      小明为机器人配置了两块圆形浮垫,可以铺设在泥坑上行走,而不会消耗自身的能量。但浮垫用过不能取出再用,因而只能使用两次。

      返回机器人到达“Finish”路径上可以获得的最大能量数 。注意:机器人的能量值是可以为负数的。

        下面图示依样例数据,使用了两块浮垫获得最大能量数为:1+2+0+6+9+0+5=23 . 其路径用蓝色线条标注。 




Input

第一行两个整数 m 与 n (m表示行,n表示列) 。下面 m 行每行 n 个整数 energy[i],[j]。


Output

返回机器人在路径上可以获得的最大能量数 。注意:机器人的能量值是可以为负数的。

Sample Input Copy

3 5
1 2 -3 4 -5
2 -4 6 2 6
3 2 9 -6 5

Sample Output Copy

23

HINT

  • 1<=n,m<=500
  • -1000 <= energy[i][j] <= 1000