題目描述

今年 JOI 鎮的起司工廠又開始生產起司了，一隻老鼠從巢穴裡探出頭來。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