Tehtävänanto

Tänäkin vuonna JOI-kaupungin juustotehtaat ovat aloittaneet juuston tuotannon, ja hiiri on kurkistanut ulos pesästään. JOI-kaupunki on kaavoitettu kortteleihin itä-länsi- ja pohjois-eteläsuunnassa, ja jokainen kortteli on joko pesä, juustotehdas, este tai tyhjä tontti. Hiiri lähtee liikkeelle pesästä, vierailee kaikissa juustotehtaissa ja syö $1$ juustopalan jokaisessa tehtaassa.

Tässä kaupungissa on $N$ juustotehdasta, ja jokainen tehdas tuottaa vain $1$ lajia juustoa. Juuston kovuus vaihtelee tehtaittain, ja jokaista kovuutta $1$:stä $N$:ään tuottaa täsmälleen $1$ juustotehdas.

Hiiren alkuvoimakkuus on $1$, ja joka kerta kun se syö $1$ juustopalan, sen voimakkuus kasvaa $1$:llä. Hiiri ei kuitenkaan voi syödä juustoa, joka on kovempaa kuin sen hetkinen voimakkuus.

Hiiri voi siirtyä idässä, lännessä, etelässä tai pohjoisessa olevaan viereiseen kortteliin $1$ minuutissa, mutta se ei voi mennä kortteliin, jossa on este. Se voi myös kulkea juustotehtaan läpi syömättä juustoa. Kirjoita ohjelma, joka selvittää lyhimmän ajan, joka kuluu kaikkien juustojen syömiseen. Aika, jonka hiiri käyttää juuston syömiseen, voidaan jättää huomiotta.

Syöte

Syöte koostuu $H+1$ rivistä. $1$. rivillä on $3$ kokonaislukua $H$, $W$, $N$ ($1 \le H \le 1000$, $1 \le W \le 1000$, $1 \le N \le 9$) tässä järjestyksessä välilyönnein erotettuina. Jokaisella rivillä $2$. riviltä riville $H+1$ on merkkijono, joka koostuu $W$ merkistä joukosta S, 1, 2, $\dots$, 9, X, ., ja joista kukin kuvaa vastaavan korttelin tilaa. Jos merkitsemme pohjoisesta lukien $i$. ja lännestä lukien $j$. korttelia merkinnällä $(i, j)$ ($1 \le i \le H, 1 \le j \le W$), niin rivin $i+1$ $j$. merkki on S, jos kortteli $(i, j)$ on pesä, X, jos se on este, ., jos se on tyhjä tontti, ja vastaavasti 1, 2, $\dots$, 9, jos se on tehdas, joka tuottaa kovuuden $1, 2, \dots, 9$ juustoa. Syötteessä on $1$ kutakin seuraavista: pesä sekä kovuuden $1, 2, \dots, N$ juustoa tuottavat tehtaat. Muiden ruutujen taataan olevan esteitä tai tyhjiä tontteja. Taataan, että hiiri pystyy syömään kaikki juustot.

Tuloste

Tulosta $1$ riville kokonaisluku, joka ilmaisee lyhimmän ajan (minuutteina), joka kuluu kaikkien juustojen syömiseen.

Esimerkkisyötteet ja -tulosteet

Esimerkkisyöte 1

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

Esimerkkituloste 1

4

Esimerkkisyöte 2

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

Esimerkkituloste 2

12

Esimerkkisyöte 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.......

Esimerkkituloste 3

91