D. Noodling with Knights
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

After eating a bunch of noodles, the mad hatters decide that it's time to play a quick game of chess. They play a special variant of chess where the board is completely empty except for a single knight. Furthermore, they decide that this game is too boring, so they want to play on arbitrary-sized square chess boards, not just $$$8 \times 8$$$.

Given a chess board of size $$$N \times N$$$, and a knight starting at position $$$(x_1, y_1)$$$, how many steps at minimum would it take for it to reach position $$$(x_2, y_2)$$$?

If the position is not reachable, output $$$-1$$$.

Constraints:

$$$0 \lt N \lt 800$$$

$$$0 \lt x_i, y_i \lt N$$$

Input

The first line of the input will contain just one number, N. The second line will contain two integers, $$$x_1$$$ and $$$y_1$$$, the starting position of the knight. The third line will contain three integers $$$x_2$$$ and $$$y_2$$$, the end position of the knight.

Output

The output will consist of a single integer, which is the minimum number of moves the knight needs to make to reach the end position.

If the position is not reachable, output -1.

Examples
Input
1
0 0
0 0
Output
0
Input
4
1 2
2 2
Output
3
Input
9
8 2
4 1
Output
3