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:

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.

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

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