问题

今年，JOI镇的奶酪工厂开始生产奶酪，老鼠从巢穴中冒出来。JOI镇被划分为东、西、南、北四个区域，每个区域可以是巢穴、奶酪工厂、障碍物或空地之一。老鼠从巢穴出发，依次访问每个奶酪工厂并吃掉一块奶酪。

该镇共有N个奶酪工厂，每个工厂只生产一种类型的奶酪。不同工厂生产的奶酪硬度不同，从1到N的奶酪工厂各有一个。老鼠最初的体力为1，每吃一块奶酪体力增加1。然而，老鼠不能吃比自己体力更硬的奶酪。

老鼠可以在相邻的东、西、南、北方向上移动到相邻的区域，但不能进入障碍物区域。老鼠可以跳过奶酪工厂而不吃奶酪。请编写一个程序来计算吃完所有奶酪所需的最短时间。假设老鼠吃奶酪所需的时间可以忽略不计。

输入

输入共有H + 1行。第一行包含3个整数H，W，N（1 ≤ H ≤ 1000，1 ≤ W ≤ 1000，1 ≤ N ≤ 9），以空格分隔开。第2行到第H + 1行每行包含一个长度为W的字符串，由S、1、2、...、9、X、.组成，表示各区域的状态。假设第$i$行第$j$列的字符表示区域$(i, j)$的状态（$1 ≤ i ≤ H，1 ≤ j ≤ W$），其中第$i + 1$行第j列的字符表示区域$(i, j)$是巢穴（S）、障碍物（X）或空地（.），如果是生产硬度为1、2、...、9的奶酪的工厂，则为1、2、...、9。输入确保巢穴和生产硬度为1、2、...、N的奶酪的工厂各有一个。其他格子要么是障碍物，要么是空地。

老鼠可以保证吃完所有奶酪。

输出

输出一个整数，表示吃完所有奶酪所需的最短时间（分钟）。

示例 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