以气御剑2
题号:NC219105
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

继续说回 Bear_2 要从宗门 (1,1) 前往远方 (n,m) 。(如果没有读过上一题也没有关系

Bear_2 终于算好要去远方的灵气了,但是他刚要出发就被师兄 Keven 拦住了,Keven 十分瞧不起 Bear_2 愚蠢的行为。他扔给 Bear_2 一个传送的功法,此功法可以从任意地点 A 传送到任意地点 B ,所用的灵气为 HA - HB。Bear_2 惊喜的发现如果 HA 小于 HB 时, HA - HB 小于0 既他可以回复 HB - HA 的灵气。若 HA 大于HB 则消耗 HA - H的灵气。
地图上显示每个位置 (i,j) 都有一定的海拔 Hi,j 米。他想知道到 (n,m) 最少需要多少灵力,注意有可能是负值。

输入描述:

第一行给出两个正整数 n,m (1<=n,m<=1000)
之后的 n 行,每行给出 m 个正整数 Hi,j (0<=Hi,j<=1000) 表示位置 (i,j) 的海拔

输出描述:

在一行内输出一个正整数表示到达 (n,m) 最少需要消耗的灵力
示例1

输入

复制
3 3
0 1 9
5 9 9
3 2 1

输出

复制
1