该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

你正在设计一个地下矿洞的照明系统。矿洞是一个 H 行 W 列的矩形区域，某些位置有无法穿透的岩柱（障碍物），其他位置是空的。

你可以在任意一个空位置安装一盏定向照明灯。灯光会向上、下、左、右四个方向直线传播，直到遇到岩柱或矿洞边界为止。灯光会照亮传播路径上的所有空位置（包括灯所在的位置），但不会照亮岩柱所在的位置。

你的任务是确定：安装一盏灯最多能照亮多少个位置。

输入格式

• 第一行两个整数 H 和 W。
• 接下来 H 行，每行一个长度为 W 的字符串，表示矿洞的地图：# 表示岩柱（障碍物），. 表示空位置（可以安装灯）。

输出格式

• 输出一个整数，表示安装一盏灯最多能照亮的位置数量。

样例输入 1

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

样例输出 1

6

样例输入 2

3 5
...#.
.....
#...#

样例输出 2

7

样例输入 3

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

样例输出 3

13

说明

样例 1 解释

可以安放在第 2 行第 1 列，最多可以照亮 6 格，没有更优的方案了。

数据范围

• 对于 20% 的数据，满足：1 ≤ H×W ≤ 1000；
• 对于 40% 的数据，满足：1 ≤ H×W ≤ 2000；
• 对于 100% 的数据，满足：1 ≤ H ≤ 2000，1 ≤ W ≤ 2000；
• 读入的 H 行，每行都是长度为 W 的字符串，由 # 和 . 组成，. 至少出现一次。