当前没有测试数据。

小明被困在一个 m 行 n 列的迷宫中。迷宫的每个格子里都有一个正整数。小明从起点出发，想要走到终点，且路径上所有格子（包括起点和终点）的数值之和恰好等于 w。

由于迷宫地形复杂，小明每步只能向上、下、左、右四个方向移动一格，且不能重复经过同一个格子。

小明希望找到一条满足条件的路径，并且步数尽可能少。请你帮他求出最少的步数。

输入格式 第一行两个整数 m 和 n，表示迷宫有 m 行 n 列。

第二行四个整数 qx, qy, zx, zy，分别表示起点的行、列和终点的行、列（行列均从 1 开始编号）。

第三行一个整数 w，表示路径上所有格子数值之和的目标值。

接下来 m 行，每行 n 个整数，第 i 行第 j 个数表示格子 (i, j) 的数值。

输出格式 输出一个整数，表示满足条件的最少步数。

如果不存在满足条件的路径，输出 -1。

数据范围与约定 1 ≤ m ≤ n < 900

1 ≤ qx, zx ≤ m，1 ≤ qy, zy ≤ n

每个格子的数值均为正整数

保证满足条件的路径步数一定小于 16 步（若存在解）

3 3
1 1 3 3
6
1 2 0
0 0 0
0 0 3

4