Problem F
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₁,y₁) and the tile at (x₂,y₂) 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 ≤ n ≤ 500) and k (1 ≤ k ≤ n²), where the art installation consists of an n X n matrix with tiles having numbers from 1 to k.

Each of the next n lines contains n space-separated integers x (1 ≤ x ≤ 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