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

粮仓选址

题目描述

噜噜准备在一块 $n \times m$ 的荒地上修建 简易粮仓。 为了方便施工，每座粮仓必须正好占据一个 $2 \times 3$ 的水平矩形（高 $2$ 行、宽 $3$ 列）。若矩形 $6$ 个格子全部为空地 .，就可以建粮仓；只要其中有任何岩石 #，该矩形就无法使用。

噜噜可以 至多炸掉一格岩石（把某个 # 变成 .）。 请问在最佳炸点方案下，最多有多少个位置可以建造合法粮仓？

粮仓之间可以互相重叠或相邻；题目只要求统计满足条件的 $2\times3$ 矩形总数，而不需要实际放置或去重。

输入格式

第一行两个整数，$n,m$。 接下来$n$行$m$列的字符，表示地图矩阵;

• $1\le n,m\le 1000$
• 每行 rowᵢ 为长 $m$ 的字符串，只含 . 与 #。

输出格式

一个整数，表示可建粮仓的最大数量。

样例一

输入

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

输出

7

说明

若炸掉第 $4$ 行第 $4$ 列（坐标 ($4,4$)）的岩石，可使原本包含 唯一 岩石的若干 $2\times3$ 矩形变为全空地；此时总共有 $7$ 个合法矩形。

数据范围与难度说明

• $1\le n,m\le 1000$，保证读取总输入不超过 $10^{6}$ 字符。