Uppgift

Även i år har ostfabrikerna i staden JOI börjat tillverka ost, och en mus har stuckit ut huvudet ur sitt bo. Staden JOI är indelad i kvarter i öst-västlig och nord-sydlig riktning, och varje kvarter är antingen boet, en ostfabrik, ett hinder eller en tom plats. Musen startar från boet, besöker alla ostfabriker och äter $1$ ostbit vid varje fabrik.

I den här staden finns det $N$ ostfabriker, och varje fabrik tillverkar endast $1$ sorts ost. Ostens hårdhet varierar från fabrik till fabrik, och det finns exakt $1$ ostfabrik som tillverkar ost av varje hårdhet från $1$ till $N$.

Musens ursprungliga styrka är $1$, och för varje $1$ ostbit den äter ökar dess styrka med $1$. Musen kan dock inte äta ost som är hårdare än dess nuvarande styrka.

Musen kan förflytta sig till ett intilliggande kvarter i öster, väster, söder eller norr på $1$ minut, men den kan inte gå in i ett kvarter med ett hinder. Den kan också passera en ostfabrik utan att äta osten. Skriv ett program som beräknar den kortaste tiden det tar att äta upp all ost. Tiden det tar för musen att äta själva osten kan försummas.

Indata

Indata består av $H+1$ rader. Den $1$:a raden innehåller $3$ heltal $H$, $W$, $N$ ($1 \le H \le 1000$, $1 \le W \le 1000$, $1 \le N \le 9$) i denna ordning, åtskilda av mellanslag. Varje rad från den $2$:a raden till rad $H+1$ innehåller en sträng med $W$ tecken bestående av S, 1, 2, $\dots$, 9, X, ., där varje tecken anger tillståndet för motsvarande kvarter. Om vi betecknar det $i$:te kvarteret från norr och det $j$:te kvarteret från väster som $(i, j)$ ($1 \le i \le H, 1 \le j \le W$), så är det $j$:te tecknet på rad $i+1$ lika med S om kvarteret $(i, j)$ är boet, X om det är ett hinder, . om det är en tom plats, och 1, 2, $\dots$, 9 om det är en fabrik som tillverkar ost med hårdhet $1, 2, \dots, 9$. I indata finns det $1$ vardera av boet och fabrikerna som tillverkar ost med hårdhet $1, 2, \dots, N$. Alla andra rutor garanteras vara hinder eller tomma platser. Det garanteras att musen kan äta upp all ost.

Utdata

Skriv ut på $1$ rad ett heltal som anger den kortaste tiden (i minuter) det tar att äta upp all ost.

Exempel på indata och utdata

Exempel på indata 1

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

Exempel på utdata 1

4

Exempel på indata 2

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

Exempel på utdata 2

12

Exempel på indata 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.......

Exempel på utdata 3

91