P16000 [ICPC 2020 NAC] Hopscotch

There’s a new art installation in town, and it inspires you... to play a childish game. The art installation consists of a floor with an $n \times n$ matrix of square 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 some tile numbered $2$, then $3$, and so on, until you reach some tile numbered $k$. You are a good hopper, so you can hop any required distance. You visit exactly one tile of each number from $1$ to $k$. What’s the shortest possible total distance over a complete game of Hopscotch? Use the Manhattan distance: the distance between the tile at $(x_1, y_1)$ and the tile at $(x_2, y_2)$ is $|x_1 - x_2| + |y_1 - y_2|$.

The first line of input contains two space-separated integers $n$ ($1 \le n \le 50$) 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$). This is the art installation.

Output a single integer, which is the total length of the shortest path starting from some $1$ tile and ending at some $k$ tile, or $-1$ if it isn’t possible.