치즈 (Cheese)

올해도 JOI 마을의 치즈 공장이 치즈 생산을 시작하자, 쥐가 굴에서 고개를 내밀었다. JOI 마을은 동서남북으로 구획이 나뉘어 있으며, 각 구획은 굴, 치즈 공장, 장애물, 빈 땅 중 하나이다. 쥐는 굴에서 출발하여 모든 치즈 공장을 방문해 치즈를 하나씩 먹는다.

이 마을에는 $N$개의 치즈 공장이 있고, 각 공장은 한 종류의 치즈만 생산한다. 치즈의 굳기는 공장마다 다르며, 굳기 $1$부터 $N$까지의 치즈를 생산하는 공장이 정확히 하나씩 있다.

쥐의 처음 체력은 $1$이며, 치즈를 하나 먹을 때마다 체력이 $1$씩 늘어난다. 단, 쥐는 자신의 체력보다 굳기가 큰 치즈는 먹을 수 없다.

쥐는 동서남북으로 인접한 구획으로 $1$분 만에 이동할 수 있지만, 장애물 구획에는 들어갈 수 없다. 치즈 공장을 치즈를 먹지 않고 지나갈 수도 있다. 모든 치즈를 다 먹는 데 걸리는 최단 시간을 구하는 프로그램을 작성하라. 단, 쥐가 치즈를 먹는 데 걸리는 시간은 무시한다.

입력은 $H+1$개의 행으로 이루어진다. 첫째 줄에는 세 정수 $H$, $W$, $N$ ($1 \le H \le 1000$, $1 \le W \le 1000$, $1 \le N \le 9$)이 공백으로 구분되어 주어진다. 둘째 줄부터 $H+1$번째 줄까지 각 줄에는 'S', '1', '2', ..., '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, \ldots, 9$의 치즈를 생산하는 공장이면 각각 '1', '2', ..., '9'가 된다. 입력에는 굴과 굳기 $1, 2, \ldots, N$의 치즈를 생산하는 공장이 각각 하나씩 있다. 나머지 칸은 장애물이거나 빈 땅임이 보장된다. 쥐가 모든 치즈를 먹을 수 있음이 보장된다.

모든 치즈를 다 먹는 데 걸리는 최단 시간(분)을 나타내는 정수를 한 줄에 출력하라.