Умова задачі

Цього року сироварні містечка 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