Cheese

This year, too, the cheese factories in JOI Town have started producing cheese, and a mouse has poked its head out of its nest. JOI Town is divided into a grid aligned with the four cardinal directions, and each cell is one of: a nest, a cheese factory, an obstacle, or an empty lot. The mouse starts from its nest, visits every cheese factory, and eats one piece of cheese at each.

There are $N$ cheese factories in this town, and each factory produces only one kind of cheese. The hardness of the cheese differs from factory to factory: for each hardness from $1$ to $N$, there is exactly one factory that produces cheese of that hardness.

The mouse's initial strength is $1$, and every time it eats a piece of cheese its strength increases by $1$. However, the mouse cannot eat cheese that is harder than its current strength.

The mouse can move to an adjacent cell in one of the four cardinal directions in $1$ minute, but it cannot enter an obstacle cell. It may also pass through a cheese factory without eating its cheese. Write a program that computes the shortest time needed to finish eating all of the cheese. The time it takes the mouse to eat cheese is negligible.

The input has $H+1$ lines. The first line contains three integers $H$, $W$, $N$ ($1 \le H \le 1000$, $1 \le W \le 1000$, $1 \le N \le 9$) separated by spaces. Each of the following $H$ lines (lines $2$ through $H+1$) contains a string of $W$ characters made up of 'S', '1', '2', ..., '9', 'X', and '.', each representing the state of a cell. Let $(i, j)$ denote the cell that is $i$-th from the north and $j$-th from the west ($1 \le i \le H$, $1 \le j \le W$). The $j$-th character of line $i+1$ is 'S' if cell $(i, j)$ is the nest, 'X' if it is an obstacle, '.' if it is an empty lot, and '1', '2', ..., '9' if it is a factory producing cheese of hardness $1, 2, \ldots, 9$ respectively. The input contains exactly one nest and exactly one factory for each hardness $1, 2, \ldots, N$. Every other cell is guaranteed to be an obstacle or an empty lot. It is guaranteed that the mouse can eat all of the cheese.

Output a single integer on one line: the shortest time (in minutes) needed to finish eating all of the cheese.