Lamp

题目描述

给定一个高为 $H$ 行、宽为 $W$ 列的网格。在这个网格中，部分格子存在障碍物。

すぬけ君想要在没有障碍物的格子中选择一个，并在该格子上安装一盏灯。从安装灯的格子出发，光线会沿着上下左右四个方向直线照射。对于每个方向，光线会一直照射到遇到第一个有障碍物的格子，或者到达网格边界的前一个格子为止。安装灯的格子本身也会被照亮，但有障碍物的格子不会被照亮。

すぬけ君希望通过安装灯，使被照亮的格子数最大。

给定 $H$ 个长度为 $W$ 的字符串 $S_i$（$1 \leq i \leq H$）。当 $S_i$ 的第 $j$ 个字符（$1 \leq j \leq W$）为 # 时，表示从上到下第 $i$ 行、从左到右第 $j$ 列的格子有障碍物；为 . 时表示没有障碍物。

请你求出被照亮的格子数的最大值。

输入格式

输入通过标准输入给出，格式如下：

$H$ $W$
$S_1$
$S_2$
$\vdots$
$S_H$

输出格式

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

输入输出样例 #1

输入 #1

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

输出 #1

8

输入输出样例 #2

输入 #2

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

输出 #2

13

说明/提示

限制条件

• $1 \leq H \leq 2,000$
• $1 \leq W \leq 2,000$
• $S_i$ 仅由 # 和 . 组成，长度为 $W$
• 至少存在一个 .

样例解释 1

如果すぬけ君在从上到下第 $2$ 行、从左到右第 $2$ 列的格子安装灯，则从上到下第 $2$ 行、从左到右第 $1$ 到 $5$ 列的格子，以及从左到右第 $2$ 列、从上到下第 $1$ 到 $4$ 行的格子都会被照亮，总共 $8$ 个格子。