Problem Description

This year, the cheese factory in JOI town has started producing cheese again, and the mice have come out of their nest. JOI town is divided into sections, and each section is either a nest, a cheese factory, an obstacle, or an empty space. The mice start from the nest and visit all the cheese factories to eat one cheese each.

There are \( N \) cheese factories in this town, and each factory produces only one type of cheese. The hardness of the cheese varies by factory, and there is exactly one factory for each hardness from 1 to \( N \).

The initial strength of the mice is 1, and it increases by 1 for each cheese they eat. However, the mice cannot eat cheese that is harder than their current strength.

The mice can move to adjacent sections to the east, west, north, or south in 1 minute, but they cannot enter sections with obstacles. They can pass by cheese factories without eating the cheese. Write a program to find the shortest time required for the mice to finish eating all the cheese, ignoring the time it takes to eat the cheese.

Input Format

The input consists of \( H+1 \) lines. The first line contains three integers \( H \), \( W \), and \( N \) (\( 1 \leq H \leq 1000 \), \( 1 \leq W \leq 1000 \), \( 1 \leq N \leq 9 \)) separated by spaces. From the second line to the \( H+1 \)-th line, each line contains a string of \( W \) characters consisting of S, 1, 2, ..., 9, X, or ., representing the state of each section. If the section at the \( i \)-th row from the north and the \( j \)-th column from the west is the nest, it is represented by S; if it is an obstacle, by X; if it is an empty space, by .; and if it is a factory producing cheese of hardness 1, 2, ..., 9, it is represented by 1, 2, ..., 9, respectively. The input guarantees that there is exactly one nest and one factory for each hardness from 1 to \( N \). Other sections are guaranteed to be either obstacles or empty spaces. It is guaranteed that the mice can eat all the cheese.

Output Format

Output a single integer representing the shortest time (in minutes) required to finish eating all the cheese.

Sample Input and Output

Sample Input #1

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

Sample Output #1

4

Sample Input #2

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

Sample Output #2

12

Sample Input #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.......

Sample Output #3

91

Notes/Hints

Sample Explanation 1

Sample Explanation 2

见题面 Input 部分

见题面 Output 部分