给定一个 的矩阵迷宫，其中第 行第 列的格子权值为 。 LH 起始位于 ，出口位于 。迷宫配有一个计数器，初始值为 。在任意时刻，若计数器的值满足 ，且 LH 身处出口 ，大门即刻打开，LH 得以逃离。 每经过 秒，LH 必须向上、下、左、右四个方向中的某一方向移动一步（不得停留，也不得走出迷宫）。假设 LH 从 移动到 ，则计数器会累加 。 请计算 LH 最快需要多少秒才能逃离；若无论如何都无法逃离，则输出 。
输入描述:
输入共三部分：第一行输入三个整数 ；接下来 行，每行 个整数，构成矩阵 ；再接下来 行，每行 个整数，构成矩阵 ，范围均为 。


输出描述:
输出一个整数，代表最短逃离时间；若无法逃离，输出 。
示例1

输入

3 3 10
1 2 3
0 1 4
0 0 0
1 0 0
0 0 1
0 1 0

输出

6

说明

C=\begin{bmatrix}<br /> 100 &20  &30 \\<br />  0& 10 & 400\\<br />  0& 0 &0<br />\end{bmatrix}。

第一秒，从 (1,1) 走到 (1,2)，计数器的值为 120。

第二秒，从 (1,2) 走到 (1,3)，计数器的值为 150。

第三秒，从 (1,3) 走到 (1,2)，计数器的值为 170。

第四秒，从 (1,2) 走到 (2,2)，计数器的值为 180。

第五秒，从 (2,2) 走到 (3,2)，计数器的值为 180。

第六秒，从 (3,2) 走到 (3,3)，计数器的值为 180，是 9 的倍数，逃出迷宫。

img
加载中...