Problema

Este año nuevamente las fábricas de queso de la ciudad JOI han comenzado a producir queso, y un ratón ha asomado la cabeza desde su nido. La ciudad JOI está dividida en bloques orientados de este a oeste y de norte a sur, y cada bloque es el nido, una fábrica de queso, un obstáculo o un terreno baldío. El ratón parte de su nido, visita todas las fábricas de queso y se come $1$ trozo de queso en cada una.

En esta ciudad hay $N$ fábricas de queso, y cada fábrica produce únicamente $1$ tipo de queso. La dureza del queso varía según la fábrica, y hay exactamente $1$ fábrica de queso que produce queso de cada dureza desde $1$ hasta $N$.

La energía inicial del ratón es $1$, y cada vez que se come $1$ trozo de queso, su energía aumenta en $1$. Sin embargo, el ratón no puede comer un queso más duro que su energía actual.

El ratón puede moverse a un bloque adyacente al este, oeste, sur o norte en $1$ minuto, pero no puede entrar en un bloque con un obstáculo. También puede pasar por una fábrica de queso sin comerse el queso. Escribe un programa para encontrar el tiempo mínimo necesario para terminar de comerse todos los quesos. El tiempo que tarda el ratón en comerse el queso se puede despreciar.

Entrada

La entrada consta de $H+1$ líneas. La $1$-ra línea contiene $3$ enteros $H$, $W$ y $N$ ($1 \le H \le 1000$, $1 \le W \le 1000$, $1 \le N \le 9$) en ese orden, separados por espacios. Cada línea desde la $2$-da línea hasta la línea $H+1$ contiene una cadena de $W$ caracteres formada por S, 1, 2, $\dots$, 9, X y ., cada uno de los cuales representa el estado de cada bloque. Si denotamos como $(i, j)$ ($1 \le i \le H, 1 \le j \le W$) al bloque que es el $i$-ésimo desde el norte y el $j$-ésimo desde el oeste, entonces el $j$-ésimo carácter en la línea $i+1$ es S si el bloque $(i, j)$ es el nido, X si es un obstáculo, . si es un terreno baldío, y 1, 2, $\dots$, 9 respectivamente si es una fábrica que produce queso de dureza $1, 2, \dots, 9$. En la entrada, el nido y las fábricas que producen queso de dureza $1, 2, \dots, N$ aparecen $1$ vez cada uno. Se garantiza que las demás casillas son obstáculos o terrenos baldíos. Se garantiza que el ratón puede comerse todos los quesos.

Salida

Imprime en $1$ línea un entero que represente el tiempo mínimo (en minutos) necesario para terminar de comerse todos los quesos.

Ejemplos de entrada y salida

Ejemplo de entrada 1

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

Ejemplo de salida 1

4

Ejemplo de entrada 2

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

Ejemplo de salida 2

12

Ejemplo de entrada 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.......

Ejemplo de salida 3

91