Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

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