Условие задачи

В этом году сыроварни города JOI снова начали производить сыр, и мышь высунула голову из своей норки. Город JOI распланирован по сторонам света (восток, запад, юг, север) на кварталы, каждый из которых представляет собой норку, сыроварню, препятствие или пустырь. Мышь отправляется из норки, посещает все сыроварни и съедает по $1$ кусочку сыра на каждой.

В этом городе есть $N$ сыроварен, и каждая сыроварня производит только $1$ вид сыра. Твёрдость сыра зависит от сыроварни, причём для каждой твёрдости от $1$ до $N$ существует ровно $1$ сыроварня, производящая сыр такой твёрдости.

Начальная сила мыши равна $1$, и с каждым съеденным $1$ кусочком сыра её сила увеличивается на $1$. Однако мышь не может есть сыр, твёрдость которого превышает её текущую силу.

Мышь может переместиться в соседний по сторонам света (восток, запад, юг, север) квартал за $1$ минуту, но не может заходить в квартал с препятствием. Она также может проходить через сыроварню, не съедая сыр. Напишите программу, которая находит кратчайшее время, необходимое для того, чтобы съесть весь сыр. Временем, которое мышь тратит на само поедание сыра, можно пренебречь.

Входные данные

Входные данные состоят из $H+1$ строк. В $1$-й строке через пробел записаны $3$ целых числа $H$, $W$, $N$ ($1 \le H \le 1000$, $1 \le W \le 1000$, $1 \le N \le 9$) в указанном порядке. Каждая строка со $2$-й по строку $H+1$ содержит строку из $W$ символов, состоящую из S, 1, 2, $\dots$, 9, X, ., которые описывают состояние соответствующих кварталов. Если обозначить $i$-й с севера и $j$-й с запада квартал как $(i, j)$ ($1 \le i \le H, 1 \le j \le W$), то $j$-й символ в строке $i+1$ равен S, если квартал $(i, j)$ — норка, X, если это препятствие, ., если это пустырь, и соответственно 1, 2, $\dots$, 9, если это сыроварня, производящая сыр твёрдости $1, 2, \dots, 9$. Во входных данных норка и сыроварни, производящие сыр твёрдости $1, 2, \dots, N$, встречаются ровно по $1$ разу. Гарантируется, что все остальные клетки являются препятствиями или пустырями. Гарантируется, что мышь может съесть весь сыр.

Выходные данные

Выведите в $1$ строке целое число — кратчайшее время (в минутах), необходимое для того, чтобы съесть весь сыр.

Примеры ввода и вывода

Пример ввода 1

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

Пример вывода 1

4

Пример ввода 2

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

Пример вывода 2

12

Пример ввода 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.......

Пример вывода 3

91