机器人逃生

题目描述

机器人被放置在网格的左上角，由 n 行和 m 列组成，初始在单元格(1,1)中。

在一个步骤中，它可以移动到与当前单元相邻的单元中:

(x，y)→(x，y + 1)

(x，y)→(x + 1，y)

(x，y)→(x，y-1)

(x，y)→(x-1，y)

机器人不能离开网格。

网格(sx，sy)含有致命的激光。如果机器人进入某个距离(sx，sy)小于或等于 d 的地方，它就会被蒸发掉。两个细胞(x1，y1)和(x2，y2)之间的距离是 | x1-x2 | + | y1-y2 | 。

打印机器人到达单元格(n，m)而不被蒸发或移动到网格之外的最小步数。如果无法到达单元格(n，m)，输出 -1。

激光既不在起点上，也不在终点上。起始单元与激光器的距离总是大于 d。

输入格式

一行包含5个整数 n，m，sx，sy，d(2≤ n，m ≤1000; 1≤ sx ≤ n; 1≤ sy ≤ m;0≤ d ≤ n + m)-网格的大小，包含激光的位置和激光的蒸发距离。

输出格式

打印一个整数。如果有可能从(1,1)到达单元格(n，m)而不被蒸发或移动到网格之外，那么打印机器人能够到达的最小步数。否则，打印-1。

样例 #1

样例输入 #1

2 3 1 3 0

样例输出 #1

3

样例 #2

样例输入 #2

2 3 1 3 1

样例输出 #2

-1

样例 #3

样例输入 #3

5 5 3 4 1

样例输出 #3

8