题目内容

有一台清洁机器人需要从矩形房间的左上角移动到右下角。房间被划分为 $r$ 行 $c$ 列的网格，第 $i$ 行第 $j$ 列格子的灰尘浓度记为非负整数 $d_{i,j}$。机器人从左上角 $(0,0)$ 出发，每次只能向右或向下移动一个格子，最终到达 $(r-1,c-1)$。

机器人在移动过程中，功率控制系统的功率值需要与所在格子的灰尘浓度保持一致。设机器人从格子 $A$ 移动到相邻格子 $B$，两个格子的灰尘浓度分别为 $d_A$ 和 $d_B$。完成这次移动时，功率控制系统需要将功率从 $d_A$ 调整到 $d_B$，因此产生的调节能耗为 $|d_B - d_A|$。

一条合法路线由若干次相邻移动组成，其总调节能耗等于路线上每一次移动产生的调节能耗之和。请计算在所有合法路线中，从 $(0,0)$ 到 $(r-1,c-1)$ 的最小总调节能耗。

约束条件：

• 行数 $r$ 和列数 $c$ 满足 $1 \le r, c \le 200$。
• 每个格子的灰尘浓度 $d_{i,j}$ 满足 $0 \le d_{i,j} \le 10000$。

输入描述

第一行包含两个整数 r 和 c，分别表示网格的行数和列数。

接下来 r 行，每行包含 c 个整数，表示对应格子的灰尘浓度 $d_{i,j}$。

输出描述

输出一个整数，表示从 $(0,0)$ 到 $(r-1,c-1)$ 的最小总调节能耗。

样例1

输入

1 1
42

输出

0

说明

机器人从 $(0,0)$ 出发，终点也是 $(0,0)$，因此没有发生任何移动，总调节能耗为 0。

样例2

输入

1 3
5 1 5

输出

8

说明

网格只有一行，机器人只能一直向右移动。

第一次移动从浓度 5 到 1，能耗为 $|1-5|=4$；第二次移动从浓度 1 到 5，能耗为 $|5-1|=4$。

总调节能耗为 $4+4=8$。

样例3

输入

2 2
1 2
100 3

输出

2

说明

从 $(0,0)$ 到 $(1,1)$ 有两种合法路线。

先向右再向下：$(0,0)\to(0,1)\to(1,1)$，能耗为 $|2-1|+|3-2|=1+1=2$。

先向下再向右：$(0,0)\to(1,0)\to(1,1)$，能耗为 $|100-1|+|3-100|=99+97=196$。

较小的能耗是 2，因此答案为 2。

样例4

输入

5 6
10 12 30 25 40 50
18 11 13 35 38 45
20 50 14 16 60 44
22 48 30 17 19 21
70 65 40 35 25 20

输出

14

说明

最优路径为： $(0,0)\to(0,1)\to(1,1)\to(1,2)\to(2,2)\to(2,3)\to(3,3)\to(3,4)\to(3,5)\to(4,5)$

对应的灰尘浓度依次为： $10\to12\to11\to13\to14\to16\to17\to19\to21\to20$

总调节能耗为： $2+1+2+1+2+1+2+2+1=14$