机器人可以获得的最大金币数

题目描述

探险机器人拖着装满金币的背包穿行在一座地底迷宫中，地图被划分为 $n\times m$ 个房间。走到某个房间：

• 如果标记为非负数，表示可以拾取对应数量的金币；
• 如果标记为负数，表示这里蹲着强盗，会抢走该数值绝对值的金币。

机器人只能向右或向下移动，从入口 $(1,1)$ 走到出口 $(n,m)$。幸运的是，机器人有一项能力：在行程中最多感化 $2$ 个强盗，使得经过这两个房间时不被抢走金币（同时该房间也不会额外给金币）。请你计算机器人最终能带出迷宫的最大金币数。

输入格式

第一行包含两个整数 $n,m$，表示迷宫行数与列数。

接下来 $n$ 行，每行包含 $m$ 个整数，表示对应房间的标记。

输出格式

输出一个整数，表示机器人能带出的最多金币数。

输入输出样例 #1

输入 #1

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

输出 #1

6

数据范围

对于 $100\%$ 的数据，$1 \le n,m \le 120$，格子内的数值满足 $-10^4 \le a_{i,j} \le 10^4$。起点和终点始终可达，机器人初始金币为 $0$。EOF