8375: DP12 龙与地下城游戏问题
[Creator : ]
Description
给定一个二维数组 map，含义是一张地图，例如，如下矩阵
-2 -3 3 -5 -10 1 0 30 -5
游戏的规则如下:
1）骑士从左上角出发，每次只能向右或向下走，最后到达右下角见到公主。
2）地图中每个位置的值代表骑士要遭遇的事情。如果是负数，说明此处有怪兽，要让骑士损失血量。如果是非负数，代表此处有血瓶，能让骑士回血。
3）骑士从左上角到右下角的过程中，走到任何一个位置时，血量都不能少于 1。为了保证骑土能见到公主，初始血量至少是多少?
1）骑士从左上角出发，每次只能向右或向下走，最后到达右下角见到公主。
2）地图中每个位置的值代表骑士要遭遇的事情。如果是负数，说明此处有怪兽，要让骑士损失血量。如果是非负数，代表此处有血瓶，能让骑士回血。
3）骑士从左上角到右下角的过程中，走到任何一个位置时，血量都不能少于 1。为了保证骑土能见到公主，初始血量至少是多少?
根据 map，输出初始血量。
Input
第一行两个正整数 $n,m\ (1≤n,m≤10^3)$。
接下来 n 行，每行 m 个整数，代表 $map_{ij}\ (-10^3≤map_{ij}≤10^3)$。
接下来 n 行，每行 m 个整数，代表 $map_{ij}\ (-10^3≤map_{ij}≤10^3)$。
Output
输出一个整数，表示答案。
Sample 1 Input
3 3
-2 -3 3
-5 -10 1
0 30 -5
Sample 1 Output
7
Sample 2 Input
2 2
1 1
1 1
Sample 2 Output
1
Sample 3 Input
6 3
24 -59 -26
-88 -89 -55
-4 -16 1
12 1 -28
-4 -24 2
-23 29 -12
Sample 3 Output
80
HINT
相同题目：牛客网。