Problemstellung

Auch in diesem Jahr haben die Käsefabriken in der Stadt JOI mit der Käseproduktion begonnen, und eine Maus hat ihren Kopf aus ihrem Nest gestreckt. Die Stadt JOI ist in Ost-West- und Nord-Süd-Richtung in Planquadrate unterteilt, wobei jedes Planquadrat entweder das Nest, eine Käsefabrik, ein Hindernis oder ein freies Feld ist. Die Maus startet in ihrem Nest, besucht alle Käsefabriken und frisst jeweils $1$ Stück Käse.

In dieser Stadt gibt es $N$ Käsefabriken, und jede Fabrik produziert genau $1$ Sorte Käse. Die Härte des Käses unterscheidet sich je nach Fabrik, und für jede Härte von $1$ bis $N$ gibt es genau $1$ Käsefabrik, die Käse dieser Härte produziert.

Die anfängliche Ausdauer der Maus beträgt $1$, und jedes Mal, wenn sie $1$ Stück Käse frisst, erhöht sich ihre Ausdauer um $1$. Allerdings kann die Maus keinen Käse fressen, der härter als ihre aktuelle Ausdauer ist.

Die Maus kann sich in $1$ Minute auf ein in Ost-, West-, Süd- oder Nordrichtung benachbartes Planquadrat bewegen, darf jedoch kein Planquadrat mit einem Hindernis betreten. Sie kann eine Käsefabrik auch durchqueren, ohne den Käse zu fressen. Schreiben Sie ein Programm, das die kürzeste Zeit berechnet, die benötigt wird, bis aller Käse aufgefressen ist. Die Zeit, die die Maus zum Fressen des Käses benötigt, kann vernachlässigt werden.

Eingabe

Die Eingabe besteht aus $H+1$ Zeilen. Die $1$. Zeile enthält $3$ ganze Zahlen $H$, $W$ und $N$ ($1 \le H \le 1000$, $1 \le W \le 1000$, $1 \le N \le 9$) in dieser Reihenfolge, getrennt durch Leerzeichen. Jede Zeile von der $2$. Zeile bis zur Zeile $H+1$ enthält eine Zeichenkette aus $W$ Zeichen, bestehend aus S, 1, 2, $\dots$, 9, X und ., die jeweils den Zustand eines Planquadrats darstellen. Bezeichnet man das $i$-te Planquadrat von Norden und $j$-te Planquadrat von Westen mit $(i, j)$ ($1 \le i \le H, 1 \le j \le W$), so ist das $j$-te Zeichen in der Zeile $i+1$ gleich S, falls das Planquadrat $(i, j)$ das Nest ist, X, falls es ein Hindernis ist, ., falls es ein freies Feld ist, und jeweils 1, 2, $\dots$, 9, falls es eine Fabrik ist, die Käse der Härte $1, 2, \dots, 9$ produziert. In der Eingabe kommen das Nest sowie die Fabriken für Käse der Härte $1, 2, \dots, N$ jeweils $1$-mal vor. Es wird garantiert, dass alle anderen Felder Hindernisse oder freie Felder sind. Es wird garantiert, dass die Maus allen Käse fressen kann.

Ausgabe

Geben Sie in $1$ Zeile eine ganze Zahl aus, die die kürzeste Zeit (in Minuten) angibt, bis aller Käse aufgefressen ist.

Ein-/Ausgabebeispiele

Eingabebeispiel 1

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

Ausgabebeispiel 1

4

Eingabebeispiel 2

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

Ausgabebeispiel 2

12

Eingabebeispiel 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.......

Ausgabebeispiel 3

91