โจทย์ปัญหา

ในปีนี้โรงงานชีสในเมือง 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