題目描述

今年 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