Hossam 买了一块新的地面,长度为 $$$n$$$,宽度为 $$$m$$$,他将其分成 $$$n \cdot m$$$ 网格,每个单元格的大小为 $$$1\times1$$$。
由于 Hossam 的名字以字母“H”开头,因此他决定通过在地面的一些正方形上建造 $$$1\times1$$$ 大小的墙壁来绘制大写字母“H”。地面上的每个方格 $$$1\times1$$$ 都被分配了一个质量等级:完美、中等或差。
建造墙壁以形成字母“H”的过程具有以下限制:
- 该信件必须由一根水平线和两条垂直线组成。
- 垂直线不得位于同一列或相邻列中。
- 垂直线必须在同一行开始并在同一行结束(因此具有相同的长度)。
- 水平线应连接垂直线,但不得交叉。
- 水平线可以位于垂直线之间的任何一行(不仅在中间),顶部和底部除外。 (顶行的水平线字母看起来像“n”,底行的字母看起来像“U”。)
- 禁止在质量差的牢房内建造围墙。
- 您最多可以使用一格中等质量的方块。
- 您可以使用任意数量的完美质量的方块。
找出可用于绘制字母“H”的最大墙壁数。
查看注释以获取更多说明。
输入
输入的第一行包含两个整数 $$$n$$$, $$$m$$$ ($$$1 \le n, m \le 400$$$)。
输入的接下来的 $$$n$$$ 行每行包含 $$$m$$$ 个字符,描述网格。字符“.”代表完全正方形,字符“m”代表中等正方形,字符“#”代表坏正方形。
输出
打印一个整数 - 形成大写字母“H”的墙壁的最大数量。
如果无法绘制任何字母“H”,请打印 $$$0$$$。
示例
输入 #1
2 3 #m. .#.
输出 #1
0
输入 #2
7 8 ...#.m.. ..m...m. .#..#.m# ...m..m. m....... ..#.m.mm ......m.
输出 #2
16
注意
在第一个测试用例中,我们无法构建字母“H”。
对于第二个测试用例,下图表示网格和一些有效字母“H”。完美、中等和糟糕的方格分别用白色、黄色和黑色表示。