Oppgave

Også i år har ostefabrikkene i byen JOI begynt å produsere ost, og en mus har stukket hodet ut av boet sitt. Byen JOI er delt inn i kvartaler i retningene øst, vest, sør og nord, og hvert kvartal er enten boet, en ostefabrikk, en hindring eller en åpen plass. Musen starter fra boet, besøker alle ostefabrikkene og spiser $1$ ostebit på hver fabrikk.

I denne byen er det $N$ ostefabrikker, og hver fabrikk produserer bare $1$ type ost. Hardheten på osten varierer fra fabrikk til fabrikk, og det finnes nøyaktig $1$ ostefabrikk som produserer ost av hver hardhet fra $1$ til $N$.

Musens opprinnelige styrke er $1$, og for hver $1$ ostebit den spiser, øker styrken med $1$. Musen kan imidlertid ikke spise ost som er hardere enn dens nåværende styrke.

Musen kan bevege seg til et nabokvartal i øst, vest, sør eller nord på $1$ minutt, men den kan ikke gå inn i et kvartal med en hindring. Den kan også passere en ostefabrikk uten å spise osten. Skriv et program som finner den korteste tiden det tar å spise opp all osten. Tiden musen bruker på selve spisingen kan neglisjeres.

Inndata

Inndata består av $H+1$ linjer. Den $1$. linjen inneholder $3$ heltall $H$, $W$, $N$ ($1 \le H \le 1000$, $1 \le W \le 1000$, $1 \le N \le 9$) i denne rekkefølgen, atskilt med mellomrom. Hver linje fra den $2$. linjen til linje $H+1$ inneholder en streng med $W$ tegn bestående av S, 1, 2, $\dots$, 9, X, ., som hver representerer tilstanden til et kvartal. Hvis vi betegner det $i$-te kvartalet fra nord og det $j$-te kvartalet fra vest som $(i, j)$ ($1 \le i \le H, 1 \le j \le W$), er det $j$-te tegnet på linje $i+1$ lik S hvis kvartalet $(i, j)$ er boet, X hvis det er en hindring, . hvis det er en åpen plass, og henholdsvis 1, 2, $\dots$, 9 hvis det er en fabrikk som produserer ost med hardhet $1, 2, \dots, 9$. I inndataene finnes det $1$ hver av boet og fabrikkene som produserer ost med hardhet $1, 2, \dots, N$. Det garanteres at alle andre ruter er hindringer eller åpne plasser. Det garanteres at musen kan spise all osten.

Utdata

Skriv ut på $1$ linje et heltall som representerer den korteste tiden (i minutter) det tar å spise opp all osten.

Eksempler på inndata og utdata

Eksempel på inndata 1

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

Eksempel på utdata 1

4

Eksempel på inndata 2

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

Eksempel på utdata 2

12

Eksempel på inndata 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.......

Eksempel på utdata 3

91