Verkefni

Í ár hafa ostaverksmiðjurnar í JOI-bæ aftur hafið framleiðslu á osti og mús hefur stungið kollinum út úr hreiðri sínu. JOI-bær er skipulagður í reiti í áttirnar austur, vestur, suður og norður, og hver reitur er annaðhvort hreiðrið, ostaverksmiðja, hindrun eða auð lóð. Músin leggur af stað frá hreiðrinu, heimsækir allar ostaverksmiðjurnar og borðar $1$ ostbita í hverri þeirra.

Í þessum bæ eru $N$ ostaverksmiðjur og hver verksmiðja framleiðir aðeins $1$ tegund af osti. Hörkustig ostsins er mismunandi eftir verksmiðjum og það er nákvæmlega $1$ ostaverksmiðja sem framleiðir ost af hverju hörkustigi frá $1$ til $N$.

Upphafsþrek músarinnar er $1$ og í hvert sinn sem hún borðar $1$ ostbita eykst þrek hennar um $1$. Hins vegar getur músin ekki borðað ost sem er harðari en núverandi þrek hennar.

Músin getur fært sig yfir á aðliggjandi reit í austri, vestri, suðri eða norðri á $1$ mínútu, en hún getur ekki farið inn á reit með hindrun. Hún getur einnig farið í gegnum ostaverksmiðju án þess að borða ostinn. Skrifið forrit til að finna stysta tímann sem það tekur að klára að borða allan ostinn. Líta má framhjá tímanum sem það tekur músina að borða ostinn.

Inntak

Inntakið samanstendur af $H+1$ línum. Í $1$. línu eru $3$ heiltölur $H$, $W$, $N$ ($1 \le H \le 1000$, $1 \le W \le 1000$, $1 \le N \le 9$) í þessari röð, aðskildar með bilum. Hver lína frá $2$. línu til línu $H+1$ inniheldur streng af lengd $W$ sem samanstendur af S, 1, 2, $\dots$, 9, X, ., þar sem hvert tákn lýsir ástandi viðkomandi reits. Ef við táknum $i$-ta reitinn að norðan og $j$-ta reitinn að vestan sem $(i, j)$ ($1 \le i \le H, 1 \le j \le W$), þá er $j$-ti stafurinn í línu $i+1$ jafn S ef reitur $(i, j)$ er hreiðrið, X ef hann er hindrun, . ef hann er auð lóð, og 1, 2, $\dots$, 9 ef hann er verksmiðja sem framleiðir ost af hörkustigi $1, 2, \dots, 9$. Í inntakinu kemur hreiðrið og hver verksmiðja sem framleiðir ost af hörkustigi $1, 2, \dots, N$ fyrir $1$ sinni. Tryggt er að allir aðrir reitir séu hindranir eða auðar lóðir. Tryggt er að músin geti borðað allan ostinn.

Úttak

Skrifið út í $1$ línu heiltölu sem táknar stysta tímann (í mínútum) sem það tekur að klára að borða allan ostinn.

Dæmi um inntak og úttak

Inntaksdæmi 1

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

Úttaksdæmi 1

4

Inntaksdæmi 2

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

Úttaksdæmi 2

12

Inntaksdæmi 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.......

Úttaksdæmi 3

91