문제

올해도 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$ 번째 줄까지의 각 줄에는 S, 1, 2, $\dots$, 9, X, . 로 이루어진 $W$ 글자의 문자열이 적혀 있으며, 각각이 각 구획의 상태를 나타낸다. 북쪽에서 $i$ 번째, 서쪽에서 $j$ 번째 구획을 $(i, j)$ 라고 표기하기로 하면 ($1 \le i \le H, 1 \le j \le W$), $i+1$ 번째 줄의 $j$ 번째 문자는 구획 $(i, j)$ 가 둥지인 경우 S 가 되고, 장애물인 경우 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