Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
D. Vanya and Treasure

time limit per test

1.5 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputVanya 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}|.

Input

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

Output

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

Examples

Input

3 4 3

2 1 1 1

1 1 1 1

2 1 1 3

Output

5

Input

3 3 9

1 3 5

8 9 7

4 6 2

Output

22

Input

3 4 12

1 2 3 4

8 7 6 5

9 10 11 12

Output

11

Codeforces (c) Copyright 2010-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/19/2022 19:39:53 (g2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|