题目描述

现在有一个 $n*m$ 的方格图。每个方格上铭刻了一个有编号的传送阵。 小核桃初始位于方格图的一个位置，他想要移动到另一个位置。

小核桃每次可以选择：

• 花费一个金币，移动到上下左右相邻的方格中；
• 不花费金币，使用传送阵，传送到具有相同编号传送阵的方格中。

小核桃只能至多传送 $k$ 次。现在小核桃想知道他最少要花费多少金币。

输入格式

第一行三个正整数 $n, m, k$，表示方格图的大小为 $n$ 行 $m$ 列，小核桃最多可以传送 $k$ 次。 第二行四个正整数，前两个正整数 $x_1, y_1$ 表示小核桃的初始位置（$x_1$ 行 $y_1$ 列），后两个正整数 $x_2, y_2$ 表示小核桃想要到达的位置（$x_2$ 行 $y_2$ 列）。 接下来 $n$ 行，每行 $m$ 个数字，表示方格图上每个位置所铭刻的传送阵的编号。

输出格式

一行一个正整数，表示小核桃最少需要花费多少金币

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

提示

样例说明

最少需要三个金币。路线如下： 其中红色是花费金币移动，蓝色是传送。

数据范围