Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

P172PROA - ROUND 2A - Ma trận rương báu

Một lần dạo chơi ở Valoran, Lều có gặp và quen một người bạn đến từ Hư Không : Kassadin. Được Lều cứu mạng Kassadin cảm kích và chỉ cho Lều thuật “Hư vô bộ pháp”, và chỉ cho Lều đến kho báu xứ Valoran.

Kho báu xứ Valoran là một ma trận n hàng m cột đánh số từ 1, chia đều thành các phòng, mỗi phòng chứa một chiếc rương, mỗi chiếc rương được đánh dấu bởi 1 số nguyên dương trong khoảng từ 1đến p. Tuy nhiên, trong số n*m phòng đó chỉ có duy nhất một rương được đánh số p, cũng là số lớn nhất trong các số được đem đi đánh dấu … đó chính là chiếc rương duy nhất chứa kho báu.

Muốn mở được một rương bất kỳ đánh số x, Lều phải có được chìa khóa từ rương đánh số (x-1) và mấu chốt để Lều lấy được kho báu chính là Lều đã được tặng chiếc chìa khóa số 0 ( mở được rương loại 1) , chiếc chìa khóa mà Kassadin lấy được từ chiếc rương HEXTECH cùi mía ở quê nhà.

Ban đầu Lều đứng ở phòng chỉ số (1;1) – hàng 1 , cột 1. Các phòng được ngăn cách với nhau và không có đường đi qua, và đây là lúc để Lều sử dụng “Hư vô bộ pháp” đã học được. Lều có thể dịch chuyển bất kỳ từ ô (x1;y1) tới (x2;y2) trên ma trận và mỗi lần sử dụng Lều sẽ tốn lượng Mana được tính theo công thức :      |x1 – x2 | + |y1 – y2|

Thời buổi xăng lên giá nên Mana bán cũng rất đắt, hãy tính lượng Mana ít nhất Lều cần có để có thể lấy được kho báu. Biết rằng luôn có cách để mở được kho báu.

Input

Dòng đầu tiên chứa 3 số nguyên dương n,m,p (1<= n,m<=300 , 1<=p<=n*m) – lần lượt là số hàng, số cột của ma trận và số p – số loại rương có thể có trên ma trận

Mỗi dòng trong n dòng tiếp theo gồm m số nguyên biểu thị ma trận kho báu : a[i][j] ( 1<=a[i][j] <=p) là số thứ tự của rương trong mỗi phòng. Và chỉ có một phòng chứa rương đánh số p.

Output

Một số nguyên duy nhất là lượng mana nhỏ nhất mà Lều cần có để lấy được kho báu.

Example

Test 1:
Input:
3 4 3
2 1 1 1
1 1 1 1
2 1 1 3
Output:
5
Test 2:
Input:
3 4 12
1 2 3 4
8 7 6 5
9 10 11 12
Output:
11


Được gửi lên bởi:adm
Ngày:2017-02-23
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 ASM64 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.