配点 : $400$ 点

問題文

縦 $H$ 行横 $W$ 列のグリッドが与えられます。このグリッドのうち、いくつかのマスには障害物が存在します。

すぬけ君は、障害物のないマスのうち一つを選び、そのマスに明かりを設置しようとしています。 設置されたマスから、上下左右の四方向にまっすぐに光線が伸びます。それぞれの方向について、最初に障害物が存在するマスにぶつかる、もしくはグリッドの端にぶつかる手前のマスまで照らされます。明かりを設置したマスも照らされますが、障害物が存在するマスは照らされません。

すぬけ君は明かりによって照らされるマスの個数を最大化したいです。

$H$ 個の長さ $W$ の文字列 $S_i$ ($1 \leq i \leq H$) が与えられます。$S_i$ の $j$ 文字目 ($1 \leq j \leq W$) が # のとき、グリッドの上から $i$ 行目で左から $j$ 列目のマスには障害物があり、 . のときは障害物がありません。

照らされるマスの個数の最大値を求めてください。

制約

• $1 \leq H \leq 2,000$
• $1 \leq W \leq 2,000$
• $S_i$ は # と . のみからなる長さ $W$ の文字列
• $S_i$ ($1 \leq i \leq H$) のうちいずれかに . は最低 $1$ つ存在する

入力

入力は以下の形式で標準入力から与えられる。

$H$ $W$

$S_1$

$:$

$S_H$

出力

照らされるマスの個数の最大値を出力せよ。

4 6
#..#..
.....#
....#.
#.#...

8

すぬけ君が上から $2$ 行目、左から $2$ 列目のマスに明かりを設置すると、上から $2$ 行目のうち左から $1$ 〜 $5$ 列目のマス、 左から $2$ 列目のうち上から $1$ 〜 $4$ 列目のマス全てが照らされ、全部で $8$ マスです。

8 8
..#...#.
....#...
##......
..###..#
...#..#.
##....#.
#...#...
###.#..#

13