Есептің шарты

Биыл да JOI қалашығындағы ірімшік зауыттары ірімшік өндіруді бастады, ал тышқан өз інiнен басын шығарды. JOI қалашығы шығыс, батыс, оңтүстік және солтүстік бағыттар бойынша телімдерге бөлінген, әрбір телім ін, ірімшік зауыты, кедергі немесе бос жер болып табылады. Тышқан іннен шығып, барлық ірімшік зауыттарына барып, әрқайсысынан $1$ ірімшіктен жейді.

Бұл қалашықта $N$ ірімшік зауыты бар және әр зауыт тек $1$ түрлі ірімшік өндіреді. Ірімшіктің қаттылығы зауытқа байланысты әртүрлі, және қаттылығы $1$-ден $N$-ге дейінгі ірімшікті өндіретін дәл $1$ ірімшік зауытынан бар.

Тышқанның бастапқы күші $1$-ге тең, және ол әрбір $1$ ірімшікті жеген сайын оның күші $1$-ге артады. Алайда тышқан өзінің ағымдағы күшінен қаттырақ ірімшікті жей алмайды.

Тышқан шығыс, батыс, оңтүстік немесе солтүстік жақтағы көршілес телімге $1$ минутта өте алады, бірақ кедергісі бар телімге кіре алмайды. Ол ірімшік зауытынан ірімшікті жемей-ақ өтіп кете де алады. Барлық ірімшікті жеп бітіруге кететін ең аз уақытты табатын программа жазыңыз. Тышқанның ірімшікті жеуіне кететін уақытты ескермеуге болады.

Кіріс деректері

Кіріс деректері $H+1$ жолдан тұрады. $1$-ші жолда бос орын арқылы бөлінген $3$ бүтін сан $H$, $W$, $N$ ($1 \le H \le 1000$, $1 \le W \le 1000$, $1 \le N \le 9$) осы ретпен жазылған. $2$-ші жолдан $H+1$-ші жолға дейінгі әрбір жолда әр телімнің күйін білдіретін S, 1, 2, $\dots$, 9, X, . таңбаларынан тұратын ұзындығы $W$ жол жазылған. Солтүстіктен санағанда $i$-ші, батыстан санағанда $j$-ші телімді $(i, j)$ деп белгілесек ($1 \le i \le H, 1 \le j \le W$), онда $i+1$-ші жолдың $j$-ші таңбасы $(i, j)$ телімі ін болғанда S, кедергі болғанда X, бос жер болғанда ., ал қаттылығы $1, 2, \dots, 9$ болатын ірімшік өндіретін зауыт болғанда сәйкесінше 1, 2, $\dots$, 9 болады. Кіріс деректерінде ін және қаттылығы $1, 2, \dots, N$ ірімшік өндіретін зауыттардың әрқайсысы $1$-ден ғана бар. Басқа ұяшықтардың кедергі немесе бос жер екендігіне кепілдік беріледі. Тышқанның барлық ірімшікті жей алатынына кепілдік беріледі.

Шығыс деректері

$1$ жолда барлық ірімшікті жеп бітіруге кететін ең аз уақытты (минутпен) білдіретін бүтін санды шығарыңыз.

Кіріс және шығыс мысалдары

Кіріс мысалы 1

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

Шығыс мысалы 1

4

Кіріс мысалы 2

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

Шығыс мысалы 2

12

Кіріс мысалы 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.......

Шығыс мысалы 3

91