24596번 - 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?

입력

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 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.

제한

힌트