题目描述

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