Treść zadania

W tym roku fabryki sera w miasteczku JOI znów rozpoczęły produkcję sera, a mysz wychyliła głowę ze swojego gniazda. Miasteczko JOI jest podzielone w kierunkach wschód-zachód oraz północ-południe na kwartały, a każdy kwartał jest gniazdem, fabryką sera, przeszkodą albo pustym placem. Mysz wyrusza z gniazda, odwiedza wszystkie fabryki sera i zjada po $1$ kawałku sera w każdej z nich.

W tym miasteczku znajduje się $N$ fabryk sera i każda fabryka produkuje tylko $1$ rodzaj sera. Twardość sera różni się w zależności od fabryki i dla każdej twardości od $1$ do $N$ istnieje dokładnie $1$ fabryka sera produkująca ser o tej twardości.

Początkowa siła myszy wynosi $1$, a po zjedzeniu każdego $1$ kawałka sera jej siła wzrasta o $1$. Mysz nie może jednak zjeść sera twardszego niż jej aktualna siła.

Mysz może przemieścić się na sąsiedni kwartał na wschód, zachód, południe lub północ w ciągu $1$ minuty, ale nie może wejść na kwartał z przeszkodą. Może również przejść przez fabrykę sera bez zjadania sera. Napisz program wyznaczający najkrótszy czas potrzebny na zjedzenie wszystkich serów. Czas potrzebny myszy na samo zjedzenie sera można pominąć.

Wejście

Wejście składa się z $H+1$ wierszy. W $1$. wierszu znajdują się $3$ liczby całkowite $H$, $W$, $N$ ($1 \le H \le 1000$, $1 \le W \le 1000$, $1 \le N \le 9$) w tej kolejności, oddzielone spacjami. Każdy wiersz od $2$. wiersza do wiersza $H+1$ zawiera napis złożony z $W$ znaków należących do zbioru S, 1, 2, $\dots$, 9, X, ., z których każdy opisuje stan odpowiedniego kwartału. Jeśli kwartał $i$-ty od północy i $j$-ty od zachodu oznaczymy przez $(i, j)$ ($1 \le i \le H, 1 \le j \le W$), to $j$-ty znak w wierszu $i+1$ jest równy S, gdy kwartał $(i, j)$ jest gniazdem, X, gdy jest przeszkodą, ., gdy jest pustym placem, oraz odpowiednio 1, 2, $\dots$, 9, gdy jest fabryką produkującą ser o twardości $1, 2, \dots, 9$. Na wejściu gniazdo oraz fabryki produkujące ser o twardości $1, 2, \dots, N$ występują po $1$ razie. Gwarantuje się, że pozostałe pola są przeszkodami lub pustymi placami. Gwarantuje się, że mysz może zjeść wszystkie sery.

Wyjście

Wypisz w $1$ wierszu liczbę całkowitą oznaczającą najkrótszy czas (w minutach) potrzebny na zjedzenie wszystkich serów.

Przykłady wejścia/wyjścia

Przykład wejścia 1

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

Przykład wyjścia 1

4

Przykład wejścia 2

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

Przykład wyjścia 2

12

Przykład wejścia 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.......

Przykład wyjścia 3

91