A10417 | Vanya and Treasure

Vanya is in the palace that can be represented as a grid $n×m$ . Each room contains a single chest, an the room located in the $i$ -th row and $j$ -th columns contains the chest of type $a_{ij}$ . Each chest of type $x<=p-1$ contains a key that can open any chest of type $x+1$ , and all chests of type $1$ are not locked. There is exactly one chest of type $p$ and it contains a treasure.

Vanya starts in cell $(1,1)$ (top left corner). What is the minimum total distance Vanya has to walk in order to get the treasure? Consider the distance between cell $(r_{1},c_{1})$ (the cell in the row $r_{1}$ and column $c_{1}$ ) and $(r_{2},c_{2})$ is equal to $|r_{1}-r_{2}|+|c_{1}-c_{2}|$ .

The first line of the input contains three integers $n$ , $m$ and $p$ ( $1<=n,m<=300,1<=p<=n·m$ ) — the number of rows and columns in the table representing the palace and the number of different types of the chests, respectively.

Each of the following $n$ lines contains $m$ integers $a_{ij}$ ( $1<=a_{ij}<=p$ ) — the types of the chests in corresponding rooms. It's guaranteed that for each $x$ from $1$ to $p$ there is at least one chest of this type (that is, there exists a pair of $r$ and $c$ , such that $a_{rc}=x$ ). Also, it's guaranteed that there is exactly one chest of type $p$ .

Print one integer — the minimum possible total distance Vanya has to walk in order to get the treasure from the chest of type $p$ .