# Problem G

Hopscotch 500

Do you remember the new art installation from NAC 2020? Well, that artist is at it again, on a grander scale this time, and the new artwork still inspires youâ€”to play a childish game. The art installation consists of a floor with a square matrix of tiles. Each tile holds a single number from $1$ to $k$.

You want to play hopscotch on it! You want to start on some tile numbered $1$, then hop to a tile numbered $2$, then $3$, and so on, until you reach a tile numbered $k$.

Instead of the usual Euclidean distance, define the distance between the tile at $(x_1,y_1)$ and the tile at $(x_2,y_2)$ as:

\[ \min \left[(x_1-x_2)^2, (y_1-y_2)^2\right] \]You want to hop the shortest total distance overall, using this new distance metric. Note that a path with no hops is still a path, and has length $0$. What is the length of the shortest path?

## Input

The first line of input contains two space-separated integers $n$ ($1 \le n \le 500$) and $k$ ($1\le k\le n^2$), where the art installation consists of an $n\! \times \! n$ matrix with tiles having numbers from $1$ to $k$.

Each of the next $n$ lines contains $n$ space-separated integers $x$ ($1 \le x \le k$). These are the numbers in the art installation.

## Output

Output a single integer, which is the total length of the shortest path from any $1$ tile to any $k$ tile using our distance metric, or $-1$ if no such path exists.

Sample Input 1 | Sample Output 1 |
---|---|

10 5 5 1 3 4 2 4 2 1 2 1 4 5 3 4 1 5 3 1 1 4 4 2 4 1 5 4 5 2 4 1 5 2 1 5 5 3 5 2 3 2 5 5 2 3 2 3 1 5 5 5 3 4 2 4 2 2 4 4 2 3 1 5 1 1 2 5 4 1 5 3 2 2 4 1 2 5 1 4 3 5 5 3 2 1 4 3 5 2 3 1 3 4 2 5 2 5 3 4 4 2 |
0 |

Sample Input 2 | Sample Output 2 |
---|---|

10 30 18 13 30 15 18 16 14 1 5 5 17 18 7 30 14 30 13 14 1 28 28 24 7 23 9 10 5 12 21 6 11 16 6 2 27 14 1 26 7 21 16 2 9 26 6 24 22 12 8 16 17 28 29 19 4 6 21 19 6 22 11 27 11 26 13 23 10 3 18 6 14 19 9 8 17 6 16 22 24 1 12 19 10 21 1 8 20 24 29 21 21 29 1 23 23 24 6 20 25 17 |
19 |