题目描述

徐老师和蛋蛋公主刚刚用尽了九牛二虎之力，终于逃出了那条令人窒息的暗黑长廊。他们以为即将重获自由，然而命运似乎并不打算如此轻易地放过他们。就在他们松一口气的瞬间，一道耀眼的光芒突然亮起，将他们紧紧包裹。

当光芒散去，他们发现自己置身于一个陌生而神秘的空间——一个$H×W$的魔法矩阵中。这个矩阵由无数闪烁着奇异光芒的元素组成，每一个元素都蕴含着强大的魔法力量。矩阵中的光线交错穿梭，形成一幅幅复杂而美丽的图案，仿佛在诉说着古老的魔法故事。

徐老师和蛋蛋公主站在矩阵中的一个随机位置，四周是无尽的魔法波动。他们能感受到这些波动中蕴含的强大能量，同时也意识到，要想离开这个矩阵，他们必须解开其中的奥秘。两人相视一笑，眼中闪烁着坚定的光芒。他们知道，无论前方有多少困难和挑战，只要携手并肩，就一定能够找到出路。魔法有 $H$行 $W$ 列，矩阵中只有三种字符，第 $i$ 行第 $j$ 列的字符$A[i][j]=$'#'， 表示此方格不可通行，若$A[i][j] =$'.' ，表示此方格可以通行，若$A[i][j]$='S' ，表示徐老师和蛋蛋公主的起始位置。

他们想要逃出魔法矩阵，即要到达第$1$行或第$H$行或第$1$列或第$W$列。于是蛋蛋公主就发挥了作用，她会一种魔法，使用这 种魔法一次能做如下两件事：

1. 最多$K$次移动，每次移动到相邻（上、下、左、右）的可通行的方格，也可以一次都不移动；
2. 选择最多$K$个不可通行的方格，将它们全变成永久可通行的方格，也可以一个方格都不选择。

请你算一下 蛋蛋公主至少需要使用多少次魔法，才能逃出魔法矩阵，到达边界（即到达第$1$行或第$H$行或第$1$列或第$W$列）。

输入格式

第一行三个整数$H, W, K$。

接下来$H$行，每行 $W$个字符描述矩阵。

输出格式

输出一行包含一个整数，表示 蛋蛋公主 至少使用魔法的次数。。

3 3 3
#.#
#S.
###

1

7 7 2
#######
#######
##...##
###S###
##.#.##
###.###
#######

2

数据范围

• $100\%$的数据： $3 ≤ H ≤ 1000 ，3 ≤ W ≤ 1000 ，1 ≤ K ≤ H \times W$。
• 数据保证矩阵中只有一个'S' ，且不在矩阵的第$1$行或第 $H$ 行或第$1$列或第 $W$列。