Vanya và Kho Báu

Vanya đang ở trong một cung điện được biểu diễn bằng lưới $n\times m$. Mỗi ô chứa đúng một rương, rương ở hàng $i$ cột $j$ có loại $a_{ij}$.

Mỗi rương có loại $x\le p-1$ chứa một chiếc chìa khóa mở được mọi rương loại $x+1$. Tất cả rương loại $1$ không bị khóa. Có đúng một rương loại $p$ và nó chứa kho báu.

Vanya xuất phát từ ô $(1,1)$ (góc trên trái). Khoảng cách giữa hai ô $(r_1,c_1)$ và $(r_2,c_2)$ là $|r_1-r_2|+|c_1-c_2|$ (khoảng cách Manhattan). Tính tổng quãng đường nhỏ nhất Vanya phải đi để đến được rương loại $p$.

Vanya phải mở rương theo thứ tự loại tăng dần: trước tiên đến một rương loại $1$, rồi một rương loại $2$, …, rồi rương loại $p$. Tại mỗi bước, Vanya có thể di chuyển tự do trên lưới (không có chướng ngại); chỉ cần lượt thăm các rương đúng thứ tự loại.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên $n$, $m$, $p$.
• $n$ dòng tiếp theo, mỗi dòng gồm $m$ số nguyên $a_{ij}$ — loại của rương tại ô $(i,j)$.

Dữ liệu ra

In ra một số nguyên — tổng quãng đường nhỏ nhất.

Ràng buộc

• $1\le n,m\le 300$
• $1\le p\le n·m$
• $1\le a_{ij}\le p$
• Với mọi $x$ từ $1$ đến $p$, tồn tại ít nhất một rương loại $x$.
• Có đúng một rương loại $p$.

Ví dụ