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 thò đầu ra khỏi tổ. Thị trấn được chia thành các ô theo các hướng đông, tây, nam, bắc. Mỗi ô là tổ chuột, nhà máy phô mai, chướng ngại vật hoặc đất trống. Chú chuột xuất phát từ tổ, ghé thăm tất cả các nhà máy và ăn một miếng phô mai ở mỗi nhà máy.

Thị trấn có \(N\) nhà máy phô mai, mỗi nhà máy chỉ sản xuất một loại phô mai. Độ cứng của phô mai ở các nhà máy khác nhau là khác nhau: với mỗi độ cứng từ \(1\) đến \(N\), có đúng một nhà máy sản xuất phô mai có độ cứng đó.

Ban đầu, sức lực của chú chuột là \(1\). Mỗi lần ăn một miếng phô mai, sức lực của chú tăng thêm \(1\). Tuy nhiên, chú không thể ăn phô mai có độ cứng lớn hơn sức lực hiện tại của mình.

Yêu cầu

Chú chuột có thể di chuyển đến một ô kề theo hướng đông, tây, nam hoặc bắc trong \(1\) phút, nhưng không được đi vào ô có chướng ngại vật. Chú cũng có thể đi qua một nhà máy mà không ăn phô mai ở đó. Hãy viết chương trình tìm thời gian ngắn nhất để chú ăn hết tất cả các miếng phô mai. Có thể bỏ qua thời gian ăn phô mai.

Dữ liệu vào

Dữ liệu gồm \(H+1\) dòng:

• Dòng \(1\) chứa ba số nguyên \(H\), \(W\), \(N\) theo thứ tự này, cách nhau bởi dấu cách.
• Mỗi dòng từ \(2\) đến \(H+1\) chứa một xâu gồm \(W\) ký tự thuộc tập S, 1, 2, \(\ldots\), 9, X, ., mô tả trạng thái của các ô.

Gọi ô ở vị trí thứ \(i\) tính từ phía bắc và thứ \(j\) tính từ phía tây là \((i,j)\), với \(1 \le i \le H\) và \(1 \le j \le W\). Ký tự thứ \(j\) trên dòng \(i+1\) mô tả ô \((i,j)\) như sau:

• S: tổ chuột.
• X: chướng ngại vật.
• .: đất trống.
• 1, 2, \(\ldots\), 9: nhà máy sản xuất phô mai có độ cứng tương ứng là \(1\), \(2\), \(\ldots\), \(9\).

Đầu vào có đúng một tổ chuột và đúng một nhà máy cho mỗi độ cứng \(1\), \(2\), \(\ldots\), \(N\). Các ô còn lại đều là chướng ngại vật hoặc đất trống. Bảo đảm chú chuột có thể ăn hết tất cả các miếng phô mai.

Dữ liệu ra

In ra một dòng chứa một số nguyên là thời gian ngắn nhất, tính bằng phút, để chú chuột ăn hết tất cả các miếng phô mai.

Ràng buộc

• \(1 \le H \le 1000\).
• \(1 \le W \le 1000\).
• \(1 \le N \le 9\).

Ví dụ

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

4

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

12

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.......

91