题目描述

高桥被锁在一座建筑物里。

这座建筑物由 $H×W$ 个房间组成，按照 $H$ 行 $W$ 列排列。我们将第 $i$ 行第 $j$ 列的房间表示为 $(i,j)$。房间的状态用字符 $A_{i,j}$ 表示。如果 $A_{i,j}=$ #，表示该房间被锁住，无法进入；如果 $A_{i,j}=$ .，表示该房间未锁住，可以自由进入。高桥目前位于 $A_{i,j}=$ S 的房间中，该房间也可以自由进入。

第 $1$ 行、第 $1$ 列、第 $H$ 行或第 $W$ 列的每个房间都有一个出口。其他房间 $(i,j)$ 连接着四个房间：$(i-1,j)$、$(i+1,j)$、$(i,j-1)$ 和 $(i,j+1)$。

高桥会使用他的魔法来离开这座建筑物。每次施法，他可以进行以下操作：

• 最多移动到相邻房间 $K$ 次，最少 $0$ 次。在此过程中，无法进入被锁住的房间。
• 然后，选择并解锁至多 $K$ 个被锁住的房间，最少 $0$ 个。从那时起，这些房间将保持解锁状态。

高桥的目标是到达一个有出口的房间。找到达到此目标所需的最小施法次数。

保证高桥最初位于一个没有出口的房间。

约束条件

• $3 ≤ H ≤ 800$
• $3 ≤ W ≤ 800$
• $1 ≤ K ≤ H×W$
• 每个 $A_{i,j}$ 是 #、. 或 S。
• 存在唯一的 $(i,j)$ 使得 $A_{i,j}=$ S，并且满足 $2 ≤ i ≤ H-1$ 和 $2 ≤ j ≤ W-1$。

输入

输入从标准输入读取，格式如下：

$H$ $W$ $K$ $A_{1,1}A_{1,2}$...$A_{1,W}$ : $A_{H,1}A_{H,2}$...$A_{H,W}$

输出

打印达到目标所需的最小施法次数。

示例输入 1

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

示例输出 1

1

高桥可以在一次施法中移动到房间 $(1,2)$。

示例输入 2

3 3 3
###
#S#
###

示例输出 2

2

高桥在第一次施法中无法移动，但可以解锁房间 $(1,2)$。然后，在下一次施法中，他可以移动到房间 $(1,2)$，在两次施法中达到了目标。

示例输入 3

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

示例输出 3

2