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 aij. 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 (r1, c1) (the cell in the row r1 and column c1) and (r2, c2) is equal to |r1 - r2| + |c1 - c2|.

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 aij (1 ≤ aij ≤ 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 arc = 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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.ListIterator;
import java.util.StringTokenizer;

/** Class: VanyaAndTreasure.java
 *  @author
 *  @version 1.0 <p>
 *  Course:
 *  Written / Updated: Jun 12, 2016
 *
 *  This Class - See VanyaAndTreasure.pdf for instructions.
 *  VERDICT: (most likely correct but not fast enough)
 *  Consider a modified dynamic programming or BFS, or in the alternative
 *  try a tighter heuristic for A*?
 *
 *  UPDATE: Tried a tighter heuristic for A*...not good. The time it takes to compute a tighter heuristic for A*
 *  might as well be used to compute all pairs shortest paths, which takes too long anyway.
 *
 *  UPDATE 2: Dynamic programming takes too long where there are lots of rooms of chest type x and/or lots of rooms of chest type x+1.
 *  In this case, a sweep of all the rooms with a BFS / Dyn-programming combo is more efficient.
 *
 *  UPDATED VERDICT: PASS
 */
public class VanyaAndTreasure {

	/**
	 * This class describes the room at a certain (x,y) location in the grid.
	 * @author PP
	 *
	 */
	private class Cell implements Comparable<Cell>{
//		private int type;	//the chest type (from 1 to p inclusive) that this cell contains.
		private int row, col; 	//row / col index of this room cell.
		private int distance;	//Used for the original bfs() method ONLY. Has no relation to the global shortestDist[][] array!
//		private int pos1D;

		Cell(int type,int row, int col) {
//			this.type = type;
			this.row = row;
			this.col = col;
//			this.pos1D = m * row + col;
			this.distance = Integer.MAX_VALUE;
		}

		/* For debugging only */
		@Override
		public String toString() {
			return String.format("(%s, %s) dist: %s", row, col, distance);
		}

		@Override
		public int compareTo(Cell c) {
			return this.distance - c.distance;
		}
	}
	//end private class Cell

	/*** BEGIN class VanyaAndTreasure ***/
	/* the number of rows and columns in the table representing the palace and
	 * the number of different types of the chests, respectively, where
	 * (1 <= n, m <= 300, and 1 <= p <= n*m) */
	private int n, m, p;
	private Cell[][] roomArr;		//Keeps track of Cell in every room at location (i,j)
	private int[][] shortestDist;	//Keeps track of shortest possible distance to room location at (i,j)

	/* Will map each chest type (from 1 to p, inclusive) to a list of ALL rooms
	 * in which that chest is located.
	 * NOTE: the rooms will be saved in the form of a single integer that represents
	 * the row and column values.
	 *
	 * EXAMPLE: if a chest type 2 is located in rooms (2,3) and (1,0), and
	 * the rooms are in a 4x4 grid, then the array will save the following:
	 * chestTypeToRoomLocation[2] = {11, 4}
	 *
	 * where (2,3) is represented as 2*4+3 = 11, and
	 * (1,0) is represented as 1*4+0 = 4.
	 * */
	LinkedList<Integer>[] chestTypeToRoomLocation;

	/* An Array containing Arrays of neighboring cells for rooms of given chest type x.
	 * neighboringCellsAscending[x] = {All Cells containing chest of type x+1} */
	Cell[][] neighboringCellsAscending;

	/* The goal destination Cell, which has chest type p (where p is the last integer in a given input problem). */
	Cell destinationCell;

	/**
	 * constructor.
	 */
	@SuppressWarnings("unchecked")
	public VanyaAndTreasure() {
		try {
			BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));

            //Read the first line
            String line = rd.readLine();

            StringTokenizer tokenizer = new StringTokenizer(line);
            this.n = Integer.parseInt(tokenizer.nextToken());
            this.m = Integer.parseInt(tokenizer.nextToken());
            this.p = Integer.parseInt(tokenizer.nextToken());

            /* Read what this array of LinkedLists is all about near the top of this file.
             * Allocating p + 1 space as we'll have the index go from 1 to p inclusive. */
            //Unavoidable warning; flaw of Java generics. Used SuppressWarning() at the top of this constructor method.
            this.chestTypeToRoomLocation = (LinkedList<Integer>[])new LinkedList<?>[this.p + 1];

            /* Initialize room Array */
            this.roomArr = new Cell[n][m];

            /* Read the next n lines. Each line will have m entries. Use these values to
             * create a 2-D array roomArr. */
            for (int i = 0; i < n; i++) {
            	line = rd.readLine();
            	tokenizer = new StringTokenizer(line);
            	for (int j = 0; j < m; j++) {
            		int chestType = Integer.parseInt(tokenizer.nextToken());
            		this.roomArr[i][j] = new Cell(chestType, i, j);	//create new room

            		LinkedList<Integer> tempList = chestTypeToRoomLocation[chestType];

            		/* if Array above hasn't yet created the linkedlist associated with this chestType,
            		 * initialize a new linked list, then add the current room to the linkedlist */
    				if (tempList == null) {
    					tempList = new LinkedList<>();
    					chestTypeToRoomLocation[chestType] = tempList;
    				}
    				tempList.add(i * m + j);	//Add this room to the linkedlist associated with the hashmap

    				/* If the value we read pertains to the final chest type p, then we know
    				 * that this is the ultimate destination, and that there is only ONE chest
    				 * of this type. So let's save this cell for future reference. */
    				if (chestType == this.p) {
    					this.destinationCell = this.roomArr[i][j];
    				}
            	}
            	//end for j
            }
            //end for i

            this.shortestDist = new int[n][m];
            for (int i = 0; i < shortestDist.length; i++) {
            	Arrays.fill(shortestDist[i], 99999999);
            }

            this.neighboringCellsAscending = new Cell[p][];

            //Print out the final answer
            System.out.println(this.shortestDistIterative());

            rd.close();
		} catch (IOException ioe) {
			ioe.printStackTrace();
		}
	}

	private int shortestDistIterative() {
		/* Let's initialize the "shortest" distances for rooms with chest type 1.
		 * Since Vanya always begins at (0,0), it's trivial to initialize these distances. */
		Cell[] cellsWithChestType1 = neighboringCellsAscending[0];
		if (cellsWithChestType1 == null || cellsWithChestType1.length == 0) {	//if no neighbors have been initialized yet...
			cellsWithChestType1 = getNeighboringCells(0, true);	//invoke custom method
			neighboringCellsAscending[0] = cellsWithChestType1;	//and save it to the array so we don't do same computation twice
		}
		for (Cell cellWithChestType1 : cellsWithChestType1) {
			shortestDist[cellWithChestType1.row][cellWithChestType1.col] = cellWithChestType1.row + cellWithChestType1.col;
		}

		for (int i = 1; i < p; ++i) {
			Cell[] neighbors = neighboringCellsAscending[i];
			if (neighbors == null) {	//if no neighbors have been initialized yet...
				neighbors = getNeighboringCells(i, true);	//invoke custom method
				neighboringCellsAscending[i] = neighbors;	//and save it to the array so we don't do same computation twice
			}

			Cell[] prevNeighbors = neighboringCellsAscending[i - 1];

			/* If there are too many of these types of rooms, a bfs is more efficient */
			if (prevNeighbors.length * neighbors.length >= this.n * this.m) {
				this.bfs2(prevNeighbors, neighbors);
			/* Otherwise, this dyn. programming method is efficient enough. */
			} else {
				for (Cell neighbor : neighbors) {
					for (Cell prevNeighbor : prevNeighbors) {
						shortestDist[neighbor.row][neighbor.col] = Math.min(shortestDist[neighbor.row][neighbor.col],
								shortestDist[prevNeighbor.row][prevNeighbor.col] + getDist(prevNeighbor, neighbor));
					}
				}
				//end for Cell neighbor: neighbors
			}
			//end if/else
		}
		//end for i
		return shortestDist[this.destinationCell.row][this.destinationCell.col];
	}
	//end private int shortestDistIterative

	/**
	 * Method: bfs2
	 * @param prevNeighbors
	 * @param neighbors
	 * Efficient version of multiple-source and multiple-destination BFS. Better than bfs().
	 */
	private void bfs2(Cell[] prevNeighbors, Cell[] neighbors) {
		/* Initialize the temporary array of shortest distances. We'll update the global array at the end of this method. */
		int[][] distance = new int[n][m];
	    for(int i = 0; i < n; i++) for(int j = 0; j < m; j++)
	        distance[i][j] = 99999999;

	    /* Initialize the shortest possible distances for the prev. neighboring rooms.
	     * We'll propagate BFS from these locations, where we KNOW we have the shortest way of reaching them. */
	    for (Cell p : prevNeighbors)
	        distance[p.row][p.col] = shortestDist[p.row][p.col];

	    /* We'll explore all the ways in which can move either RIGHT or DOWN, and update the temporary
	     * 2D array distance accordingly. Notice we're starting from the top-left corner to ensure
	     * we explore all possibilities. */
	    for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) {
	        if (i+1 < n) distance[i + 1][j] = Math.min(distance[i + 1][j], distance[i][j] + 1);
	        if (j+1 < n) distance[i][j + 1] = Math.min(distance[i][j + 1], distance[i][j] + 1);
	    }

	    /* We'll now explore all the ways in which can move either LEFT or UP, and update the temporary
	     * 2D array distance accordingly. Note we're starting from the bottom-right corner this time. */
	    for (int i = n-1; i >= 0; i--) for (int j = m-1; j >= 0; j--) {
	        if (i-1 >= 0) distance[i - 1][j] = Math.min(distance[i - 1][j], distance[i][j] + 1);
	        if (j-1 >= 0) distance[i][j - 1] = Math.min(distance[i][j - 1], distance[i][j] + 1);
	    }

	    /* Now distance[i][j] contains the shortest possible distance for all cells, starting
	     * from any one of the cells contained in the array prevNeighbors. So we can update
	     * the global shortestDist array for the array of cells that we're concerned with, i.e. neighbors. */
	    for (Cell cell : neighbors)
	        shortestDist[cell.row][cell.col] = distance[cell.row][cell.col];
	}

	/**
	 * Method: bfs
	 * @param prevNeighbors
	 * @param neighbors
	 *
	 * UPDATE: not as efficient as bfs2() method.
	 */
//	private void bfs(Cell[] prevNeighbors, Cell[] neighbors) {
//		PriorityQueue<Cell> minPQ = new PriorityQueue<Cell>(Arrays.asList(prevNeighbors));
//		boolean[][] visited = new boolean[n][m];
//
//		/* Initialize the distance attribute for each Cell, for purposes of this BFS only. */
//		for (int i = 0; i < this.n; i++) {
//			for (int j = 0; j < this.m; j++) {
//				if (this.roomArr[i][j].type == prevNeighbors[0].type) {
//					this.roomArr[i][j].distance = this.shortestDist[i][j];
//					visited[i][j] = true;
//				}
//				else {
//					this.roomArr[i][j].distance = Integer.MAX_VALUE;
//				}
//			}
//		}
//
//		int numOfCurrNeighborsVisited = 0;
//
//		while (numOfCurrNeighborsVisited < neighbors.length) {
//			Cell currCell = minPQ.remove();
//			ArrayList<Cell> bfsNeighbors = getBFSNeighbors(currCell, visited);
//			for (Cell bfsNeighbor: bfsNeighbors) {
//				if (bfsNeighbor.distance > currCell.distance + 1) {
//					bfsNeighbor.distance = currCell.distance + 1;
//					minPQ.add(bfsNeighbor);
//					visited[bfsNeighbor.row][bfsNeighbor.col] = true;
//					if (bfsNeighbor.type == neighbors[0].type) {
//						numOfCurrNeighborsVisited++;
//					}
//				}
//			}
//			//end for Cell
//		}
//		//end while
//
//		for (Cell neighbor : neighbors) {
//			this.shortestDist[neighbor.row][neighbor.col] = neighbor.distance;
//		}
//    }
	//end private void bfs

	/**
	 * Method: getBFSNeighbors
	 * @param currCell
	 * @param visited
	 * @return
	 * Helper method for bfs(). No longer needed.
	 */
//	private ArrayList<Cell> getBFSNeighbors(Cell currCell, boolean[][] visited) {
//		int row = currCell.row;
//		int col = currCell.col;
//		int maxPossibleNeighbors = 4;
//
//		ArrayList<Cell> bfsNeighbors = new ArrayList<>();
//		int[] rowOffset = {0, 0, 1,-1};
//		int[] colOffset = {1,-1, 0, 0};
//		for (int i = 0; i < maxPossibleNeighbors; i++) {
//			int neighborRow = row + rowOffset[i];
//			int neighborCol = col + colOffset[i];
//			if (neighborRow < 0 		|| neighborCol < 0 			||
//				neighborRow >= this.n 	|| neighborCol >= this.m 	||
//				visited[neighborRow][neighborCol] == true) {
//				continue;
//			}
//			Cell bfsNeighbor = this.roomArr[neighborRow][neighborCol];
//			bfsNeighbors.add(bfsNeighbor);
//		}
//		return bfsNeighbors;
//	}

	/**
	 * Method: getNeighboringCells
	 * @param chestType
	 * @return
	 */
	private Cell[] getNeighboringCells(int chestType, boolean ascending) {
		/* All chests of type x - 1 can open chests of type x, so neighboring rooms of type x
		 * contain chests of chestType x - 1. */
		LinkedList<Integer> neighborRooms = this.chestTypeToRoomLocation[ascending? chestType + 1 : chestType - 1];
		if (neighborRooms == null) {
			return new Cell[0];
		}
		Cell[] neighbors = new Cell[neighborRooms.size()];
		ListIterator<Integer> iter = neighborRooms.listIterator();
		for (int i = 0; i < neighbors.length; i++) {
			int thisRoom = iter.next();
			int thisRow = thisRoom / this.m;
			int thisCol = thisRoom % this.m;
			neighbors[i] = this.roomArr[thisRow][thisCol];
		}
		return neighbors;
	}

	private int getDist(Cell c1, Cell c2) {
		return Math.abs(c1.row - c2.row) + Math.abs(c1.col - c2.col);
	}

	/**
	 * Method: minTotalDistToGetTreasure
	 * @return the minimum possible total distance Vanya has to walk
	 * in order to get the treasure from the chest of type this.p.
	 *
	 * This uses A*. However, since the heuristic is poor, this is inefficient.
	 * We could try to improve the heuristic, but in the time it takes to do that,
	 * we're better off just running the dynamic programming + bfs2() methods above.
	 */
//	private int minTotalDistToGetTreasure() {
//
//		/* This will save all neighboring cells for a given chest type for easy reference and efficiency. */
////		this.neighboringCells = new HashMap<>();
////
////		/* Might be worth it to try something like A* for this one...
////		 * First set the neighbors of each chest type in all the rooms */
////		for (int i = 0; i < this.roomArr.length; i++) {
////			for (int j = 0; j < this.roomArr[i].length; j++) {
////				Cell thisCell = this.roomArr[i][j];
////				int chestType = thisCell.type;
////
////				//Set all the neighbors
////				Cell[] neighbors = neighboringCells.get(chestType);	//get the neighbors from the hashmap above
////				if (neighbors == null) {	//if no neighbors have been initialized yet...
////					neighbors = getNeighboringCells(chestType);	//invoke custom method
////					neighboringCells.put(chestType, neighbors);	//and save it to the hashmap so we don't do same computation twice
////				}
//////				thisCell.neighborArr = neighbors;	//set the neighbors for this cell
////
////				/* Set the estimated manhattan distance from this cell to destination cell,
////				 * provided that the manhattan distance cannot be shorter than the difference
////				 * between destination chest type and this chest type.
////				 *
////				 * For example, if this cell type == 2 and destination cell type == 5,
////				 * it will take at least 3 unlocking steps to get to the destination chest.
////				 * So, if the manhattan distance between this cell and destination cell is only 2,
////				 * we still have to set the est. distance at 3. */
//////				thisCell.estDistRemaining = Math.max(
//////						this.destinationCell.type - thisCell.type,
//////						Math.abs(this.destinationCell.row - thisCell.row) + Math.abs(this.destinationCell.col - thisCell.col));
////				thisCell.computeEstDist();
////
////			}
////			//end for j
////		}
//		//end for i
//
//		/* Since we start at the upper leftmost corner -- i.e. the location (0,0) -- we'll first get
//		 * the locations of all the rooms with chest type 1 in it (remember, these chest types don't need keys)
//		 * and set them as the initial "neighbors".
//		 *
//		 * We call the below method with parameter 0 (although technically there is no chestType with value 0)
//		 * because doing so will give us an array of all the cells that have chestType 1. */
//
//		Cell[] initialNeighbors = this.getNeighboringCells(0);
//
//		/* Now put these in a prioritylist. Since the Cell objects implement the Comparable interface,
//		 * they will be "sorted" from smallest to largest in the priorityqueue. */
//		PriorityQueue<Cell> pq = new PriorityQueue<>(Arrays.asList(initialNeighbors));
//
//		/* Testing priorityquee */
////		while (!pq.isEmpty()) {
////			System.out.println(pq.remove());
////		}
//
//		Cell currRoom = null;
//
//		/* Begin A* algorithm */
//		HashSet<Cell> openList = new HashSet<>(pq);
//		HashSet<Cell> closedList = new HashSet<>();
//		while (currRoom != this.destinationCell && !pq.isEmpty()) {
//			currRoom = pq.remove();
//			currRoom.visited = true;
//			openList.remove(currRoom);
//			closedList.add(currRoom);
//			Cell[] neighbors = neighboringCells.get(currRoom.type);
//			for (Cell neighbor: neighbors) {
//				if (!neighbor.visited && neighbor.distSoFar > currRoom.distSoFar + this.getDist(currRoom, neighbor)) {
//					neighbor.distSoFar = currRoom.distSoFar + this.getDist(currRoom, neighbor);
//					pq.remove(neighbor);
//					pq.add(neighbor);
//					openList.add(neighbor);
//				}
//			}
//			//end for
//		}
//		//end while
//
//		if (currRoom == this.destinationCell) {
//			return currRoom.distSoFar + currRoom.estDistRemaining;
//		}
//		return -1;
//	}

	public static void main(String[] args) {
		new VanyaAndTreasure();
//		System.out.println(vt.minTotalDistToGetTreasure());
	}
}
