Deadly Laser
Contest: Educational Codeforces Round 134 (Rated for Div. 2)
Difficulty rating: 1000
Tags: implementation

The robot is placed in the top left corner of a grid, consisting of $$$n$$$ rows and $$$m$$$ columns, in a cell $$$(1, 1)$$$.

In one step, it can move into a cell, adjacent by a side to the current one:

- $$$(x, y) \rightarrow (x, y + 1)$$$;
- $$$(x, y) \rightarrow (x + 1, y)$$$;
- $$$(x, y) \rightarrow (x, y - 1)$$$;
- $$$(x, y) \rightarrow (x - 1, y)$$$.

The robot can't move outside the grid.

The cell $$$(s_x, s_y)$$$ contains a deadly laser. If the robot comes into some cell that has distance less than or equal to $$$d$$$ to the laser, it gets evaporated. The distance between two cells $$$(x_1, y_1)$$$ and $$$(x_2, y_2)$$$ is $$$|x_1 - x_2| + |y_1 - y_2|$$$.

Print the smallest number of steps that the robot can take to reach the cell $$$(n, m)$$$ without getting evaporated or moving outside the grid. If it's not possible to reach the cell $$$(n, m)$$$, print -1.

The laser is neither in the starting cell, nor in the ending cell. The starting cell always has distance greater than $$$d$$$ to the laser.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of testcases.

The only line of each testcase contains five integers $$$n, m, s_x, s_y, d$$$ ($$$2 \le n, m \le 1000$$$; $$$1 \le s_x \le n$$$; $$$1 \le s_y \le m$$$; $$$0 \le d \le n + m$$$) — the size of the grid, the cell that contains the laser and the evaporating distance of the laser.

The laser is neither in the starting cell, nor in the ending cell ($$$(s_x, s_y) \neq (1, 1)$$$ and $$$(s_x, s_y) \neq (n, m)$$$). The starting cell $$$(1, 1)$$$ always has distance greater than $$$d$$$ to the laser ($$$|s_x - 1| + |s_y - 1| > d$$$).

Output format:
For each testcase, print a single integer. If it's possible to reach the cell $$$(n, m)$$$ from $$$(1, 1)$$$ without getting evaporated or moving outside the grid, then print the smallest amount of steps it can take the robot to reach it. Otherwise, print -1.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
3
2 3 1 3 0
2 3 1 3 1
5 5 3 4 1

Example output:
3
-1
8

Editorial:
First, let's determine if it's possible to reach the end at all. If the laser's field doesn't span until any wall, then it's surely possible — just stick to the wall yourself.
If it touches at most one wall, it's still possible. If it's the bottom wall or the left wall, then take the path close to the top and the right wall. Vice versa, if it's the top wall or the right wall, then take the path close to the bottom and the left wall.
What if both of these paths are locked? That means that the laser touches at least two walls at the same time: the top one and the left one, or the bottom one and the right one. Turns out, it's completely impossible to reach the end in either of these two cases. Just draw a picture and see for yourself.
Thus, we can always take at least one of the path sticking to the walls. The distance from the start to the end is $$$|n - 1| + |m - 1|$$$, and both of these paths are exactly this long. So the answer is always either -1 or $$$n + m - 2$$$.
To check if the laser touches a wall with its field, you can either use a formula or check every cell adjacent to a wall.
Overall complexity: $$$O(1)$$$ or $$$O(n + m)$$$ per testcase.