$1 \le x,y \le n$ を満たす点 $(x,y)$ からなる $n \times n$ の格子で、UFO を操縦している。通れない点 (*) と通れる点 (.) がある。

最初は点 $(1,1)$ におり、できるだけ早く $(n,n)$ に到達することを目指す。点 $(x,y)$ にいるとき、1 秒で $(x+1,y)$, $(x,y+1)$, $(x-1,y)$, $(x,y-1)$、または任意の非負整数 $i \le k$ に対する $f^i(x,y)$ にテレポートできる。関数 $f^i(x,y)$ は以下のように定義される：

$$ f^i(x,y)=\begin{cases}(x,y)&(i=0),\\f^{i-1}(y+1,x)&(i>0).\end{cases} $$

移動先が格子の外であるか、通れない点である場合はテレポートできない。

$(n,n)$ に到達するために必要な最小時間を求めよ。$(n,n)$ に到達できない場合は -1 を出力せよ。

入力

入力の最初の行には 2 個の整数 $n$ と $k$ が与えられる ($1 \le n,k \le 5000$)。

続く $n$ 行にはそれぞれ、格子を表す $n$ 個の文字が与えられる。

点 $(1,1)$ と $(n,n)$ は通れることが保証される。

出力

$(n,n)$ に到達するための最小時間を表す整数を 1 行に 1 つ出力せよ。到達できない場合は -1 を出力せよ。

入出力例

入力 1

3 2
.*.
.*.
...

出力 1

3

入力 2

3 3
.*.
.*.
...

出力 2

2