Đề bài

Năm nay, các nhà máy phô mai ở thị trấn JOI lại bắt đầu sản xuất phô mai, và một chú chuột đã ló đầu ra khỏi tổ. Thị trấn JOI được quy hoạch thành các ô theo hướng đông, tây, nam, bắc, và mỗi ô là tổ chuột, nhà máy phô mai, chướng ngại vật hoặc bãi đất trống. Chú chuột xuất phát từ tổ, ghé thăm tất cả các nhà máy phô mai và ăn $1$ miếng phô mai ở mỗi nhà máy.

Trong thị trấn này có $N$ nhà máy phô mai, và mỗi nhà máy chỉ sản xuất $1$ loại phô mai duy nhất. Độ cứng của phô mai khác nhau tùy theo từng nhà máy, và có đúng $1$ nhà máy sản xuất phô mai cho mỗi độ cứng từ $1$ đến $N$.

Thể lực ban đầu của chú chuột là $1$, và mỗi khi ăn $1$ miếng phô mai, thể lực của chú tăng thêm $1$. Tuy nhiên, chú chuột không thể ăn phô mai cứng hơn thể lực hiện tại của mình.

Chú chuột có thể di chuyển sang ô liền kề theo hướng đông, tây, nam hoặc bắc trong $1$ phút, nhưng không thể đi vào ô có chướng ngại vật. Chú cũng có thể đi ngang qua một nhà máy phô mai mà không ăn phô mai. Hãy viết chương trình tìm thời gian ngắn nhất để chú chuột ăn hết tất cả phô mai. Lưu ý rằng thời gian chú chuột ăn phô mai có thể bỏ qua.

Dữ liệu vào

Dữ liệu vào gồm $H+1$ dòng. Dòng thứ $1$ chứa $3$ số nguyên $H$, $W$, $N$ ($1 \le H \le 1000$, $1 \le W \le 1000$, $1 \le N \le 9$) theo thứ tự đó, cách nhau bởi dấu cách. Mỗi dòng từ dòng thứ $2$ đến dòng thứ $H+1$ chứa một xâu gồm $W$ ký tự tạo bởi S, 1, 2, $\dots$, 9, X, ., biểu thị trạng thái của từng ô. Nếu ký hiệu ô thứ $i$ tính từ phía bắc và thứ $j$ tính từ phía tây là $(i, j)$ ($1 \le i \le H, 1 \le j \le W$), thì ký tự thứ $j$ ở dòng thứ $i+1$ là S nếu ô $(i, j)$ là tổ chuột, là X nếu là chướng ngại vật, là . nếu là bãi đất trống, và lần lượt là 1, 2, $\dots$, 9 nếu là nhà máy sản xuất phô mai có độ cứng $1, 2, \dots, 9$. Trong dữ liệu vào, tổ chuột và các nhà máy sản xuất phô mai có độ cứng $1, 2, \dots, N$ mỗi loại có đúng $1$ cái. Các ô còn lại được đảm bảo là chướng ngại vật hoặc bãi đất trống. Chú chuột được đảm bảo có thể ăn hết tất cả phô mai.

Dữ liệu ra

In ra trên $1$ dòng một số nguyên biểu thị thời gian ngắn nhất (tính bằng phút) để ăn hết tất cả phô mai.

Ví dụ

Ví dụ đầu vào 1

3 3 1
S..
...
..1

Ví dụ đầu ra 1

4

Ví dụ đầu vào 2

4 5 2
.X..1
....X
.XX.S
.2.X.

Ví dụ đầu ra 2

12

Ví dụ đầu vào 3

10 10 9
.X...X.S.X
6..5X..X1X
...XXXX..X
X..9X...X.
8.X2X..X3X
...XX.X4..
XX....7X..
X..X..XX..
X...X.XX..
..X.......

Ví dụ đầu ra 3

91