1457: splay1的香料运输
Memory Limit：512 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：56
Solved：10
Description
为了发动巴特勒圣战以完成对厄拉科斯的统治，保罗决定将厄拉科斯上残存的香料采集起来并运往南方部族，然而圣战在即，保罗决定只采集一处地区的香料并且他希望从起点到南方部族的路径最短，同时他还要躲避路径上的沙虫和哈克南人。
为简化这个问题，假设厄拉科斯为一个 $n$×$m$ 的矩阵，保罗出发的起点为 $(1,1)$ ,终点为 $(n,m)$ ,保罗每次可以从从当前所在网格可以行走到上下左右的网格中，但不能移动到网格的边界之外或者是沙虫和哈克南人出现的地方。更正式的说，如果他在坐标为 $(i,j)$ 的网格里，他可以选择 $(i,j+1),(i,j-1),(i+1,j),(i-1,j)$ 四个方向行走。
在位置 $(i,j)$ 上有一个权值 $w_{i,j}$ ,表示香料的纯净度,保罗每次出发都会用预知能力确定一个权值 $x$ ,只有纯净度为 $x$ 的质因子的香料才能发挥作用。若 $w_{i,j}$ 为 $-1$ 则表示此处有沙虫或哈克南人。假设相邻网格的距离均为 $1$ ,保罗想知道带一个纯净度为 $x$ 的质因子的香料去终点所需要的最短距离是多少，如果不存在任意一条这样的路径，则输出"May thy knife chip and shatter"。
为简化这个问题，假设厄拉科斯为一个 $n$×$m$ 的矩阵，保罗出发的起点为 $(1,1)$ ,终点为 $(n,m)$ ,保罗每次可以从从当前所在网格可以行走到上下左右的网格中，但不能移动到网格的边界之外或者是沙虫和哈克南人出现的地方。更正式的说，如果他在坐标为 $(i,j)$ 的网格里，他可以选择 $(i,j+1),(i,j-1),(i+1,j),(i-1,j)$ 四个方向行走。
在位置 $(i,j)$ 上有一个权值 $w_{i,j}$ ,表示香料的纯净度,保罗每次出发都会用预知能力确定一个权值 $x$ ,只有纯净度为 $x$ 的质因子的香料才能发挥作用。若 $w_{i,j}$ 为 $-1$ 则表示此处有沙虫或哈克南人。假设相邻网格的距离均为 $1$ ,保罗想知道带一个纯净度为 $x$ 的质因子的香料去终点所需要的最短距离是多少，如果不存在任意一条这样的路径，则输出"May thy knife chip and shatter"。
Input
第一行三个整数$n$,$m$,$x$。
接下来$n$行，每行$m$个整数,第$i$行第$j$个整数$w_{i,j}$.
数据范围:
$1 \leq n,m \leq 2000$
$1 \leq x \leq 1e9$
$-1 \leq w_{i,j} \leq 1e9$
数据保证起点与终点的权值为$0$
接下来$n$行，每行$m$个整数,第$i$行第$j$个整数$w_{i,j}$.
数据范围:
$1 \leq n,m \leq 2000$
$1 \leq x \leq 1e9$
$-1 \leq w_{i,j} \leq 1e9$
数据保证起点与终点的权值为$0$
Output
输出一个整数表示最短距离,如果不存在这样的路径，输出"May thy knife chip and shatter".
Sample Input Copy
3 3 6
0 1 2
1 1 -1
1 1 0Sample Output Copy
6