Problem 1013 --冒险游戏

1013: 冒险游戏

Time Limit: 2 Sec  Memory Limit: 256 MB
Submit: 318  Solved: 73
[Submit][Status][Web Board][Creator:]

Description

河海组织一场冒险游戏,该游戏将场地分为N*M的方格,每个方格内均有一个关卡,要闯过每个关卡,都需要消耗一定数量的体力
游戏的起点为(1,1) 终点为(N,M),每通过一关,可以选择右方或下方的一个关卡,顺利通过终点则挑战成功,但在任何地方体力透支(体力值<0)则挑战失败
如果要通过挑战,在开始挑战时最少需要补充多少体力?

Input

第一行两个数,分别是n m,(1<= n,m <= 3000)
后面n行,每行m个非负数,表示每个关卡需要消耗的体力 (0<= a[i][j] <= 10000)

Output

一行,表示最小体力数

Sample Input

2 2
1 2
3 4

Sample Output

7

HINT

共2条可选路径

1->2->4 7

1->3->4 8

Source

[Submit][Status]