J16 习题-4 拯救猪猪

题目描述

佩琦准备穿过一个 $N\times M$ 的网格迷宫，救出乔治。佩奇站在一个迷宫的左下角 $(m,1)$，把需要拯救的乔治放在了右上角 $(1,n)$。 1、佩琦每次只能向上或者向右走一步； 2、有些格子里有个正整数，表示有怪兽，佩琦如果碰到怪兽，就会被扣相应的血量； 3、有些格子里有个负整数，表示有蛋糕，佩琦吃了蛋糕，可以回复相应的血量（注意：生命值上限不能突破初始生命值）； 4、有些格子什么也没有，用数字 0 表示； 5、佩琦的生命值如果变成 $0$ 或者负数，则游戏失败。 请问：佩琦需要多少初始生命值才能完成拯救任务？

输入格式

第一行两个整数 $n$ 和 $m$ ，表示迷宫的尺寸是 $m$ 行 $n$ 列； 接下来 $m$ 行，每行 $n$ 个整数，表示每个格子的对应状态。

输出格式

一个整数，佩琦初始的最低生命要求。

样例输入

3 3
-10 -30 5
5 10 -1
3 3 -3

样例输出

8

样例分析

佩琦的的初始生命值最少需要8点，建议运动轨迹应该是： $(3,1) \rightarrow (3,2) \rightarrow (3,3) \rightarrow (2,3) \rightarrow (1,3)$。

数据范围

对于 $100\%$ 的数据，有 $1 \leq n,m \leq 1000$。