题目描述

一觉醒来，你穿越了，你穿越到了...

你现在身处一个奇怪的地方，地面被划分成 $n$ 行 $m$ 列的方格，其他地方都是一片虚无，你并不能在那里生存或行走，奇怪的是，每个方格上面都有一个数字 $x$。

你现在在这个方格空间的一角，记作 $(1,1)$。突然一个声音告诉你，你需要移动到你的斜对角的最远方格即 $(n,m)$，其中你每向前后左右四个方向相邻的格子移动一步，消耗的代价为 $1$；那个声音还告诉你，你有一个技能等价传送，如果你现在站立的格子上的数字是 $a$，那么你可以不消耗任何代价既可以到达任意一个具有同样数字 $a$ 的格子。如果你消耗的代价越小，你到达终点时获得的奖励越好，因此你需要消耗尽可能小的代价到达 $(n,m)$，你需要输出最小的消耗代价。

输入格式

从文件 move.in 中读入数据。

第一行两个正整数 $n,m$，分别表示地图的行数和列数。

第 $n$ 行，每行 $m$ 个正整数，其中第 $i$ 行第 $j$ 列的数字 $x_{i,j}$ 表示格子 $(i,j)$ 上的数字是 $x_{i,j}$。

输出格式

输出到文件 move.out 中。

一个整数表示从起点 $(1,1)$ 走到终点 $(n,m)$ 消耗的最小代价。

输入样例1

4 6
1 2 3 4 5 6
1 2 3 4 5 6
9 2 3 4 5 6
7 8 3 4 5 6

输出样例1

5

输入样例2

4 6
5 2 1 3 4 5
1 2 4 7 8 1 
6 6 10 11 31 14
13 12 15 55 41 23

输出样例2

3

数据范围

对于 30% 的测试数据，$1 \le n,m \le 50$，$1\le x_{i,j} \le 500$。

对于 80% 的测试数据，$1 \le x_{i,j} \le 2\times 10^5$。

对于额外的 10% 的测试数据，保证所有的 $x_{i,j}$ 均各不相同。

对于 100% 的测试数据，$1 \le n,m \le 2000$，$1 \le x_{i,j} \le 10^9$。