בעיה

גם השנה מפעלי הגבינה בעיירה JOI החלו לייצר גבינה, ועכבר הוציא את ראשו מהקן שלו. העיירה JOI מחולקת למשבצות בכיוונים מזרח, מערב, דרום וצפון, וכל משבצת היא קן, מפעל גבינה, מכשול או שטח ריק. העכבר יוצא מהקן, מבקר בכל מפעלי הגבינה ואוכל חתיכת גבינה $1$ בכל מפעל.

בעיירה זו יש $N$ מפעלי גבינה, וכל מפעל מייצר רק סוג $1$ של גבינה. קושי הגבינה שונה ממפעל למפעל, וישנו בדיוק מפעל גבינה $1$ המייצר גבינה בכל רמת קושי מ-$1$ ועד $N$.

הכוח ההתחלתי של העכבר הוא $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$ מכל אחד מהבאים: הקן והמפעלים המייצרים גבינה ברמת קושי $1, 2, \dots, N$. מובטח כי שאר המשבצות הן מכשולים או שטחים ריקים. מובטח כי העכבר יכול לאכול את כל הגבינות.

פלט

הדפיסו בשורה $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