Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-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

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-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/10/2018 12:55:55 (d1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|