一位勇敢的探险家正准备深入一个神秘的地下洞穴，寻找传说中的古代遗物。 整个洞穴系统可以看作一个二维网格。 探险家每次只能向上、下、左、右四个方向移动一格。 探险家携带的氧气瓶是有限的，最多只够支持连续行走 步。 氧气耗尽后，必须立刻找到洞穴内的氧气补给站来补充氧气，否则将无法继续前进。 在补给站，氧气可以被瞬间充满，恢复到最大值（即可再次行走 步）。 您的任务是编写一个程序，计算探险家从洞穴入口到达古代遗物所在位置所需的最短路径长度（总步数）。

输入描述:

输入包含以下部分：1. 第一行 : 洞穴的尺寸，包含两个整数 和 ，分别代表网格的行数和列数。2. 接下来的 行 : 每行包含 个整数，描述了 的洞穴网格。每个整数的含义如下：0 : 可通行的洞穴路径。1 : 无法通行的岩壁障碍。2 : 氧气补给站。3. 倒数第三行 : 两个整数 ，代表探险家出发的入口坐标（左上角为 ）。4. 倒数第二行 : 两个整数 ，代表古代遗物所在的终点坐标。5. 最后一行 : 一个整数 ，代表氧气瓶支持的最大连续移动步数。

输出描述:

输出一个整数，表示从入口到遗物所在地的最短路径长度。如果无法到达，则输出 -1 。

备注:

本题由牛友@Charles 整理上传