問題文

あなたは今,競プロ公園という公園にいます.
この公園の敷地は長方形の形をしていて,南北方向に$H$マス,東西方向に$W$マスのマス目状に,$H\times W$個の区画に分かれています.
以降,北から$r$番目で西から$c$番目の区画を区画$(r,c)$と呼ぶこととします.

あなたは区画$(1,1)$から南または東に区画を1つ分移動することを繰り返し,公園の出口に隣接する区画$(H,W)$を目指します.
ここで,あなたは(方角によらず)区画を1つ分移動するのに1分かかります.

ときに,いたずらっ子があなたを妨害することがあります.
もしあなたがいたずらっ子が待ち構えている区画に(上述の移動行為によって)移動した場合,そのいたずらっ子はあなたを抱えて区画$(1,1)$に移動し,
そこにあなたを置いていったうえで公園の外にある自宅に帰ります.
なお,いたずらっ子はとても足が速いため,彼女があなたを抱えて区画$(1,1)$まで移動し,あなたを解放するまでにかかる時間は0分としてよいです.

$H\times W$個の区画の情報が入力より与えられます.
$a_{i,j}$が'.'ならば区画$(i,j)$は何もなく,'k'ならば区画$(i,j)$にはいたずらっ子が待ち構えています.

あなたが区画$(H,W)$にたどり着くためにかかる最短の時間を$x$分とします. $x$の値を出力してください.

入力

$H\ W$
$a_{1,1}...a_{1,W}$
$:$
$a_{H,1}...a_{H,W}$

• $1 \le H,W \le 2000$
• $(H,W) \ne (1,1)$
• $H,W$は整数
• $a_{i,j} = $ '.'または$a_{i,j}=$ 'k'
• $a_{1,1}\ne$ 'k'
• $a_{H,W}\ne$ 'k'

出力

$x$の値を出力してください.
最後に改行してください.

サンプル

2 2
.k
k.

3

5 4
....
kk..
....
..kk
....

8

5 5
..kkk
k.kkk
k..kk
kk.kk
kk...

8

3 4
.kkk
k..k
kkk.

10