You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

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

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

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

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

给定 $H$ 行字符串 $S_i (1 \leq i \leq H)$，每个字符串的长度为 $W$。如果 $S_i$的第$j$个字符$(1 \leq j \leq W)$是 #，则说明从上方第$i$行第$j$列的方格上有一个障碍物;如果该字符是.，则说明该方格上没有障碍物。

请找出被灯照亮的方格数的最大可能值。

输入

第一行两个整数表示$H,W$

接下来一共$H$行，表示每行的状态。

输出

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

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

8

样例解释

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

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

13

样例解释

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

提示

$1 \leq H \leq 2000$

$1 \leq W \leq 2000$

$S_i$ 是长度为$W$的字符串，由#和.组成。

至少$S_i$中的某一个字符串中会出现。