問題文

$21$ 歳になった Shirotsume は拳で壁を破壊できるようになりました！
$H$ 行 $W$ 列の $H \times W$ マスからなるグリッドがあります。上から $H$ 行目、左から $j$ 列目のマスを $(i, j)$ として表します。
各マスの状態は文字 $S_{i, j}$ で表され、 $S_{i, j}$ = . なら マス $(i, j)$ は空きマスであり、 $S_{i, j}$ = # ならマス $(i, j)$ は壁です。ここで、入力においてマス $(1, 1)$ と $(H,W)$ は空きマスであることが保証されます。
はじめ、 Shirotsume はマス $(1, 1)$ にいます。 Shirotsume は以下に示す操作を好きな回数行うことでマス $(H, W)$ にたどり着きたいです。

• 体力を $1$ 消費し、今いるマスから上下左右に隣接する好きな空きマスに移動する。ただし、壁のマスに入ったり、グリッドの外部に出たりすることはできない。
• 体力を $R$ 消費し、拳で壁を破壊する。任意の（隣接していなくてもよい）壁のマスを選択し、そのマスを空きマスに変える。

マス $(1, 1)$ から $(H, W)$ に移動するために消費する体力として考えられる最小値を求めてください。

制約

• $2 \leq H, W \leq 1000$
• $1 \leq R \leq 1000$
• $S_{i, j}$ は . または # $(1 \leq i \leq H, 1 \leq j \leq W)$ ただし、 $S_{1, 1} = S_{H, W} =$ .

入力

H W R
S_{1,1} S_{1, 2} ... S_{1, W}
S_{2,1} S_{2, 2} ... S_{2, W}
.
.
.
S_{H, 1} S_{H, 2} ... S_{H, W}

出力

計算結果を一行に出力せよ。

サンプル

5 4 3
....
###.
....
.###
....

10

まず、体力を $3$ 消費して壁マスであるマス $(4, 4)$ を拳で破壊して空きマスに変えます。
次に、移動を $7$ 回行うことでマス $(H, W)$ へたどり着くことができます。
$10$ 未満の体力消費でマス $(H, W)$ にたどり着く方法はないので、これが答えになります。

3 6 1000
.##...
.##.#.
....#.

11