CF1771E.Hossam and a Letter

Hossam bought a new piece of ground with length $n$ and width $m$, he divided it into an $n \cdot m$ grid, each cell being of size $1\times1$.

Since Hossam's name starts with the letter 'H', he decided to draw the capital letter 'H' by building walls of size $1\times1$ on some squares of the ground. Each square $1\times1$ on the ground is assigned a quality degree: perfect, medium, or bad.

The process of building walls to form up letter 'H' has the following constraints:

• The letter must consist of one horizontal and two vertical lines.
• The vertical lines must not be in the same or neighboring columns.
• The vertical lines must start in the same row and end in the same row (and thus have the same length).
• The horizontal line should connect the vertical lines, but must not cross them.
• The horizontal line can be in any row between the vertical lines (not only in the middle), except the top and the bottom one. (With the horizontal line in the top row the letter looks like 'n', and in the bottom row like 'U'.)
• It is forbidden to build walls in cells of bad quality.
• You can use at most one square of medium quality.
• You can use any number of squares of perfect quality.

Find the maximum number of walls that can be used to draw the letter 'H'.

Check the note for more clarification.

侯萨姆购买了一块新土地，长度为 $n$、宽度为 $m$，他将其划分为一个 $n \times m$ 的网格，每个格子大小为 $1\times1$。

由于侯萨姆（Hossam）的名字以字母 'H' 开头，他决定通过在土地的某些格子上建造 $1\times1$ 的墙来绘制大写字母 'H'。土地上的每个 $1\times1$ 格子均被赋予一个质量等级：完美（perfect）、中等（medium） 或 差（bad）。

用墙构成字母 'H' 的过程需满足以下约束条件：

• 该字母必须由一条水平线段和两条竖直线段组成；
• 两条竖直线段不能位于同一列或相邻列；
• 两条竖直线段必须起始于同一行、终止于同一行（因此长度相等）；
• 水平线段应连接两条竖直线段，但不得与它们重叠（即不能覆盖竖直线段所在格子）；
• 水平线段可位于两条竖直线段之间的任意一行（不必恰好居中），但不能位于最顶行或最底行（若水平线段在最顶行，则形似字母 'n'；若在最底行，则形似字母 'U'）；
• 禁止在质量为“差”的格子上建墙；
• 最多只能使用一个质量为“中等”的格子；
• 可以使用任意数量的质量为“完美”的格子。

求能够用于绘制字母 'H' 的墙的最大数量。

更多说明请参见注释部分。

The first line of the input contains two integer numbers $n$, $m$ ($1 \le n, m \le 400$).

The next $n$ lines of the input contain $m$ characters each, describing the grid. The character '.' stands for a perfect square, the character 'm' stands for a medium square, and the character '#' stands for a bad square.

输入的第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 400$）。

接下来的 $n$ 行每行包含 $m$ 个字符，用于描述网格。字符 '.' 表示完美方格，字符 'm' 表示中等方格，字符 '#' 表示糟糕方格。

Print a single integer — the maximum number of walls that form a capital letter 'H'.

If it is not possible to draw any letter 'H', print $0$.

输出一个整数——能够构成大写字母“H”的墙壁的最大数量。

如果无法绘制任何字母“H”，则输出 $0$。

In the first test case, we can't build the letter 'H'.

For the second test case, the figure below represents the grid and some of the valid letters 'H'. Perfect, medium, and bad squares are represented with white, yellow, and black colors respectively.

在第一个测试用例中，我们无法构建字母“H”。

在第二个测试用例中，下图表示了网格以及其中一些有效的字母“H”。完美、中等和较差的方格分别用白色、黄色和黑色表示。