题目描述

在一片矩形山区里，工程师小北需要检修一座位于高处的信号塔。山区的地图是一个 $n \times m$ 的网格，每个格子有一个海拔高度 $h[i][j]$。

小北从山区左上角 $(1,\ 1)$ 出发，要前往右下角 $(n, m)$ 的信号塔位置。由于未携带专业登山设备，他只能从当前格子移动到上下左右相邻的格子，且只有当两个格子的高度差绝对值不超过 $k$ 时，才能安全通过。

请计算小北从起点到信号塔的最少移动步数（每一步只能移动到相邻格子）。若无法到达，输出 $-1$。

输入格式

第一行包含三个整数 $n$，$m$ 和 $k$，分别表示网格的行数和列数（$1 \le n, m \le 100$），以及允许的最大高度差。

接下来 $n$ 行，每行 $m$ 个整数，表示对应格子的海拔高度 $h[i][j]$（$0 \le h[i][j] \le 1000$）。

输出格式

输出一个整数，表示最少移动步数；若无法到达则输出 $-1$。

样例

3 3 1
1 10 10
2 5 6
3 4 7

6

样例解释

直接向右或向下的路径均会被高度 $10$ 的格子阻挡（例如 $|10-1|=9 > 1$，无法通过）。必须绕行，一条可行的最短路径（共 $6$ 步）为：$$(1,\ 1) \to (2,\ 1) \to (3,\ 1) \to (3,\ 2) \to (2,\ 2) \to (2,\ 3) \to (3,\ 3)$$

高度变化依次为 $|2-1|=1$，$|3-2|=1$，$|4-3|=1$，$|5-4|=1$，$|6-5|=1$，$|7-6|=1$，均 $\le 1$。

数据范围

对于 $100\%$ 的数据，$1 \le n, m \le 100$，$0 \le k \le 100$，$0 \le h[i][j] \le 1000$。