D - 灯

得分：$400$ 分

问题描述

给定一个有 $H$ 列 $W$ 行的网格，其中某些方格上有障碍物。

Snuke 将选择一个没有障碍物的方格，并在其上放置一盏灯。

在被放置的方格上，会往四个主要方向发射直线光束：上、下、左、右。在每一个方向上，光束会一直传播，直到碰到被障碍物占据的方格，或碰到网格的边界。它会照亮光线所经过的所有方格，包括灯所在的方格，但不会照亮被障碍物占据的方格。

Snuke 想要最大化被灯照亮的方格数。

给定 $H$ 行字符串 $S_i$ ($1 \leq i \leq H$)，每个字符串的长度为 $W$。如果 $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$)。

输入

输入从标准输入中读取，格式如下：

$H$ $W$

$S_1$

$\vdots$

$S_H$

输出

输出最大可能被灯照亮的方格数。

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

8

如果 Snuke 将灯放在从上往下数第二行，从左往右数第二列的方格上，那么它会照亮以下方格：从左往右数第二行的第一个到第五个方格，从上往下数第二列的第一个到第四个方格，共计八个方格。

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

13

如果 Snuke 选择灯放在了从上往下数第五行，从左往右数第五列的方格上，那么它会照亮十三个方格。