Anti-Distance

Time limit2sMemory limit256 MB

Summary

Given two free cells on a grid where every fifth cell at (2i+j, i-2j) is blocked, find the fewest side-adjacent steps between them.

Level: Medium7 of 10
Topics: Math, Implementation
Solved: No attempts yet

Problem

Consider a plane divided into unit squares with side $1$ . Choose a square and draw coordinate axes from its center, parallel to its sides.

Each fifth square contains an obstacle. The obstacles are placed in every square whose center is at $(2 i + j, i - 2 j)$ for all integers $i$ and $j$ . All other squares are free.

Amelia stands in a free square $A$ and wants to move to a free square $B$ . In one step, she can move from her square to a neighbor that shares a side with it, but only if that neighbor is free. What is the minimum number of steps Amelia must make to reach $B$ ?

Input

The first line contains two integers $x_1$ and $y_1$ , the coordinates of the starting square $A$ . The second line contains two integers $x_2$ and $y_2$ , the coordinates of the destination square $B$ . All coordinates are between $1$ and $10^{9}$ . Both squares are guaranteed to be free.

Output

Print one integer: the minimum number of steps from square $A$ to square $B$ .

Examples2

Example 1
Input
```
1 1
5 2
```
Expected output
```
7
```
Example 2
Input
```
1 1
2 5
```
Expected output
```
5
```