灯光

题目描述

给定一个纵向 $H$ 行、横向 $W$ 列的网格。网格中的一些格子里有障碍物。

Snuke 君打算选择一块没有障碍物的格子,并在那里放置一盏灯。从放置的格子出发,光线向上下左右四个方向笔直延伸。对每个方向,光线照亮到首次碰到障碍物的那个格子之前的那个格子为止,或者碰到网格边缘为止。放置灯的那个格子也会被照亮,但存在障碍物的格子不会被照亮。

Snuke 君希望被灯光照亮的格子数量尽可能多。

给定 $H$ 个长度为 $W$ 的字符串 $S_i$ ($1 \le i \le H$)。当 $S_i$ 的第 $j$ 个字符 ($1 \le j \le W$) 为 # 时,网格从上往下第 $i$ 行、从左往右第 $j$ 列的格子里有障碍物;为 . 时没有障碍物。

求被照亮的格子数量的最大值。

输入格式

输入按以下格式从标准输入给出:

$H$ $W$
$S_1$
$:$
$S_H$

输出格式

输出被照亮的格子数量的最大值。

样例

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

8

如果 Snuke 君把灯放在从上往下第 2 行、从左往右第 2 列的格子上,则从上往下第 2 行中从左往右第 1 到第 5 列的格子、以及从左往右第 2 列中从上往下第 1 到第 4 列的格子全部被照亮,共 $8$ 个格子。

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

13

数据范围

• $1 \le H \le 2{,}000$
• $1 \le W \le 2{,}000$
• $S_i$ 是由 # 和 . 组成的长度为 $W$ 的字符串
• 在 $S_i$ ($1 \le i \le H$) 中,至少存在 1 个 .