Problema

Anche quest'anno i caseifici della città di JOI hanno iniziato a produrre formaggio e un topo ha messo fuori la testa dalla sua tana. La città di JOI è suddivisa in isolati orientati da est a ovest e da nord a sud, e ciascun isolato è la tana, un caseificio, un ostacolo oppure uno spazio vuoto. Il topo parte dalla tana, visita tutti i caseifici e mangia $1$ pezzo di formaggio in ciascuno.

In questa città ci sono $N$ caseifici e ciascun caseificio produce $1$ solo tipo di formaggio. La durezza del formaggio varia a seconda del caseificio e c'è esattamente $1$ caseificio che produce formaggio per ciascuna durezza da $1$ a $N$.

L'energia iniziale del topo è $1$, e ogni volta che mangia $1$ pezzo di formaggio la sua energia aumenta di $1$. Tuttavia, il topo non può mangiare formaggio più duro della sua energia attuale.

Il topo può spostarsi in un isolato adiacente a est, ovest, sud o nord in $1$ minuto, ma non può entrare in un isolato con un ostacolo. Può anche passare per un caseificio senza mangiare il formaggio. Scrivi un programma per trovare il tempo minimo necessario per finire di mangiare tutto il formaggio. Il tempo impiegato dal topo per mangiare il formaggio è trascurabile.

Input

L'input è composto da $H+1$ righe. Nella $1$-a riga sono scritti $3$ interi $H$, $W$, $N$ ($1 \le H \le 1000$, $1 \le W \le 1000$, $1 \le N \le 9$) in quest'ordine, separati da spazi. Ciascuna riga dalla $2$-a riga alla riga $H+1$ contiene una stringa di $W$ caratteri composta da S, 1, 2, $\dots$, 9, X, ., ciascuno dei quali rappresenta lo stato di un isolato. Indicando con $(i, j)$ ($1 \le i \le H, 1 \le j \le W$) l'isolato che è l'$i$-esimo da nord e il $j$-esimo da ovest, il $j$-esimo carattere della riga $i+1$ è S se l'isolato $(i, j)$ è la tana, X se è un ostacolo, . se è uno spazio vuoto, e rispettivamente 1, 2, $\dots$, 9 se è un caseificio che produce formaggio di durezza $1, 2, \dots, 9$. Nell'input la tana e i caseifici che producono formaggio di durezza $1, 2, \dots, N$ sono presenti $1$ volta ciascuno. È garantito che tutte le altre caselle sono ostacoli o spazi vuoti. È garantito che il topo può mangiare tutto il formaggio.

Output

Stampa su $1$ riga un intero che rappresenta il tempo minimo (in minuti) necessario per finire di mangiare tutto il formaggio.

Esempi di input/output

Esempio di input 1

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

Esempio di output 1

4

Esempio di input 2

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

Esempio di output 2

12

Esempio di input 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.......

Esempio di output 3

91