المسألة

بدأت مصانع الجبن في مدينة 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