Énoncé du problème

Cette année encore, les fromageries de la ville de JOI ont commencé à produire du fromage, et une souris a pointé le bout de son museau hors de son nid. La ville de JOI est quadrillée en parcelles selon les directions est, ouest, sud et nord, et chaque parcelle est soit le nid, soit une fromagerie, soit un obstacle, soit un terrain vague. La souris part de son nid, visite toutes les fromageries et mange $1$ morceau de fromage dans chacune.

Dans cette ville, il y a $N$ fromageries, et chaque fromagerie ne produit qu'$1$ seul type de fromage. La dureté du fromage diffère selon la fromagerie, et il existe exactement $1$ fromagerie produisant du fromage de chaque dureté allant de $1$ à $N$.

L'endurance initiale de la souris est de $1$, et chaque fois qu'elle mange $1$ morceau de fromage, son endurance augmente de $1$. Cependant, la souris ne peut pas manger un fromage plus dur que son endurance actuelle.

La souris peut se déplacer vers une parcelle adjacente à l'est, à l'ouest, au sud ou au nord en $1$ minute, mais elle ne peut pas entrer dans une parcelle contenant un obstacle. Elle peut également traverser une fromagerie sans y manger de fromage. Écrivez un programme permettant de trouver le temps minimal nécessaire pour finir de manger tous les fromages. Le temps que met la souris à manger un fromage est négligeable.

Entrée

L'entrée se compose de $H+1$ lignes. La $1$-re ligne contient $3$ entiers $H$, $W$ et $N$ ($1 \le H \le 1000$, $1 \le W \le 1000$, $1 \le N \le 9$) dans cet ordre, séparés par des espaces. Chacune des lignes de la $2$-e ligne à la ligne $H+1$ contient une chaîne de $W$ caractères composée de S, 1, 2, $\dots$, 9, X et ., représentant chacune l'état de chaque parcelle. Si l'on note $(i, j)$ ($1 \le i \le H, 1 \le j \le W$) la parcelle située au $i$-e rang depuis le nord et au $j$-e rang depuis l'ouest, alors le $j$-e caractère de la ligne $i+1$ vaut S si la parcelle $(i, j)$ est le nid, X s'il s'agit d'un obstacle, . s'il s'agit d'un terrain vague, et respectivement 1, 2, $\dots$, 9 s'il s'agit d'une fromagerie produisant du fromage de dureté $1, 2, \dots, 9$. Dans l'entrée, le nid ainsi que les fromageries produisant du fromage de dureté $1, 2, \dots, N$ sont chacun présents en $1$ exemplaire. Il est garanti que les autres cases sont des obstacles ou des terrains vagues. Il est garanti que la souris peut manger tous les fromages.

Sortie

Affichez sur $1$ ligne un entier représentant le temps minimal (en minutes) nécessaire pour finir de manger tous les fromages.

Exemples d'entrée/sortie

Exemple d'entrée 1

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

Exemple de sortie 1

4

Exemple d'entrée 2

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

Exemple de sortie 2

12

Exemple d'entrée 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.......

Exemple de sortie 3

91