Mogu Mogu 2

問題文

$H$ 行 $W$ 列のグリッドがある。上から $i$ 行目 $(1 \leq i \leq H)$ 、左から $j$ 列目 $(1 \leq j \leq W)$ のマスを $(i,j)$ と呼ぶことにする。

グリッドの上におにぎりが置いてある。具体的には、 $S_{i,j}$ が # のときにマス $(i,j)$ の上におにぎりが $1$ つあり、それ以外のマスにおにぎりは置かれていない。

お腹の空いたoさんは、マス $(1,1)$ からマス $(H,W)$ まで、右方向と下方向の移動のみを繰り返しつつ、通過したマスに置かれているおにぎりを全て食べる。oさんが食べることのできるおにぎりの個数の最大値を求めよ。

制約

• $2 \leq H,W$
• $HW \leq 2 \times 10^5$
• $H,W$ は整数
• $S_{i,j}$ は # または .

入力

入力は以下のように与えられる。

H W
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}

出力

oさんが食べることのできるおにぎりの個数の最大値を1行に出力せよ。

サンプル

3 3
.##
.#.
.#.

3

次の * で与えられるような経路をたどることでおにぎりを $3$ 個食べることができます。これ以上多くのおにぎりを食べることはできないので、 $3$ を出力してください。

**#
.*.
.**

( * が移動経路、# が残ったおにぎり、 . が何もないマスを表す。)

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

2

マス $(1,1)$ やマス $(H,W)$ におにぎりが置かれていることもあります。

3 5
.....
.....
.....

0

グリッド上におにぎりが置かれていないこともあります。