Deskripsi Masalah

Tahun ini pabrik keju di Kota JOI kembali mulai memproduksi keju, dan seekor tikus memunculkan kepalanya dari sarangnya. Kota JOI ditata menjadi petak-petak menurut arah timur, barat, selatan, dan utara, dan setiap petak merupakan sarang, pabrik keju, rintangan, atau lahan kosong. Tikus berangkat dari sarang, mengunjungi semua pabrik keju, dan memakan $1$ potong keju di setiap pabrik.

Di kota ini terdapat $N$ pabrik keju, dan setiap pabrik hanya memproduksi $1$ jenis keju. Tingkat kekerasan keju berbeda-beda tergantung pabriknya, dan terdapat tepat $1$ pabrik keju yang memproduksi keju untuk masing-masing tingkat kekerasan dari $1$ sampai $N$.

Stamina awal tikus adalah $1$, dan setiap kali ia memakan $1$ potong keju, staminanya bertambah $1$. Namun, tikus tidak dapat memakan keju yang lebih keras daripada staminanya saat itu.

Tikus dapat berpindah ke petak yang bersebelahan di sebelah timur, barat, selatan, atau utara dalam waktu $1$ menit, tetapi tidak dapat memasuki petak rintangan. Ia juga dapat melewati pabrik keju tanpa memakan kejunya. Buatlah program untuk mencari waktu tersingkat yang dibutuhkan hingga semua keju habis dimakan. Waktu yang dibutuhkan tikus untuk memakan keju dapat diabaikan.

Masukan

Masukan terdiri dari $H+1$ baris. Baris ke-$1$ berisi $3$ bilangan bulat $H$, $W$, $N$ ($1 \le H \le 1000$, $1 \le W \le 1000$, $1 \le N \le 9$) secara berurutan yang dipisahkan oleh spasi. Setiap baris dari baris ke-$2$ hingga baris ke-$H+1$ berisi sebuah string sepanjang $W$ karakter yang terdiri dari S, 1, 2, $\dots$, 9, X, ., yang masing-masing menyatakan keadaan setiap petak. Jika petak ke-$i$ dari utara dan ke-$j$ dari barat dinyatakan sebagai $(i, j)$ ($1 \le i \le H, 1 \le j \le W$), maka karakter ke-$j$ pada baris ke-$i+1$ adalah S jika petak $(i, j)$ adalah sarang, X jika berupa rintangan, . jika berupa lahan kosong, dan masing-masing 1, 2, $\dots$, 9 jika berupa pabrik yang memproduksi keju dengan tingkat kekerasan $1, 2, \dots, 9$. Pada masukan, sarang serta pabrik yang memproduksi keju dengan tingkat kekerasan $1, 2, \dots, N$ masing-masing terdapat $1$ buah. Petak-petak lainnya dijamin berupa rintangan atau lahan kosong. Tikus dijamin dapat memakan semua keju.

Keluaran

Keluarkan dalam $1$ baris sebuah bilangan bulat yang menyatakan waktu tersingkat (dalam menit) yang dibutuhkan hingga semua keju habis dimakan.

Contoh Masukan dan Keluaran

Contoh Masukan 1

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

Contoh Keluaran 1

4

Contoh Masukan 2

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

Contoh Keluaran 2

12

Contoh Masukan 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.......

Contoh Keluaran 3

91