题目描述

小 A 从下界的传送门进入了末地。末地是一片由 $n \times m$ 个浮空平台组成的方格，第 $x$ 行第 $y$ 列的平台位于 $(x,y)$，每个平台上都铭刻着一个传送阵编号。

小 A 初始站在起点 $(x_1,y_1)$，他想前往终点 $(x_2,y_2)$。每一步他可以选择：

• 花费 $1$ 枚金币，走到上、下、左、右相邻的平台上；
• 不花费金币，使用脚下的传送阵，瞬移到任意一个编号相同的平台上。

由于传送阵能量有限，小 A 最多只能使用传送阵 $k$ 次。

请你计算，小 A 从起点到达终点最少需要花费多少枚金币。

输入格式

第一行三个整数 $n, m, k$，表示平台的行数、列数，以及最多可使用传送阵的次数。

第二行四个整数 $x_1, y_1, x_2, y_2$，表示起点和终点的位置。

接下来 $n$ 行，每行 $m$ 个整数，第 $x$ 行第 $y$ 个数表示平台 $(x,y)$ 上的传送阵编号。

输出格式

一行一个整数，表示最少需要花费的金币数。

样例

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

3

1 3 0
1 1 1 3
1 2 3

2

2 2 1
1 1 2 2
5 1
1 5

0

样例解释

样例 $1$：一种花费 $3$ 枚金币、$2$ 次传送的走法为：

1. 从 $(1,1)$ 走到 $(2,1)$，再走到 $(3,1)$，花费 $2$ 枚金币；
2. 在 $(3,1)$ 使用编号为 $4$ 的传送阵，瞬移到 $(4,2)$；
3. 从 $(4,2)$ 走到 $(5,2)$，花费 $1$ 枚金币；
4. 在 $(5,2)$ 使用编号为 $9$ 的传送阵，瞬移到终点 $(5,5)$。

全程共 $3$ 枚金币、$2$ 次传送，均不超过上限。可以验证不存在花费少于 $3$ 枚金币的方案。

样例 $2$：$k=0$ 时不能使用传送阵，只能行走。从 $(1,1)$ 向右走两格到达 $(1,3)$，花费 $2$ 枚金币。

样例 $3$：起点 $(1,1)$ 与终点 $(2,2)$ 的传送阵编号都是 $5$，使用一次传送阵即可直接到达，花费 $0$ 枚金币。

数据范围与约定

对于 $100\%$ 的数据，$1 \le n, m \le 1000$，$0 \le k \le 5$，$1 \le$ 传送阵编号 $\le 1000$，起点和终点均在方格内。