题目描述

有一个 $H$ 行 $W$ 列的网格。每个格子上写着 +、-、# 中的一个字符。用 $(i,j)$ 表示从上往下数第 $i$ 行、从左往右数第 $j$ 列的格子。网格由 $H$ 个长度为 $W$ 的字符串 $S_1, S_2 , \dots ,S_H$ 给出：$S_i$ 的第 $j$ 个字符写在格子 $(i,j)$ 上。

你可以进行以下操作零次或多次：

• 选择一个不是 # 的格子。把所有「从所选格子出发，只使用向左、向右或向下移动到相邻格子的移动方式，且不经过任何 # 格子就能到达」的格子全部变为 #。这里所选格子本身也算在可达格子之中。

求操作结束后网格中可能达到的下列值的最大值：+ 格子的个数减去 - 格子的个数。

输入格式

输入从标准输入给出，格式如下：

• $H$ $W$
• $S_1$
• $S_2$
• $\vdots$
• $S_H$

输出格式

输出答案。

数据范围

• $1 \le H,W \le 30$
• $S_i$ 是由 +、-、# 组成的长度为 $W$ 的字符串。
• $H$ 和 $W$ 是整数。

2 3
+-+
--+

1

如果选择 $(2,1)$，第 $2$ 行的所有格子都会变为 #（注意不能向上移动）。剩下的第 $1$ 行有两个 + 格子和一个 - 格子，所以值为 $2-1=1$，这就是最大值。

3 3
+--
-#-
#+#

1

如果选择 $(1,1)$，除 $(3, 2)$ 以外的所有格子都会变为 #。注意所选格子 $(1, 1)$ 本身也算在可达格子之中，并且不能经过 # 格子。

5 7
++#--++
-+---+#
##++-++
--#-++-
+---#++

5

• 来源：AtCoder ABC 472 G

子任务设置

• 子任务 1（$30\%$）：$H,W \le 4$。
• 子任务 2（$30\%$）：$H,W \le 15$。
• 子任务 3（$40\%$）：无特殊限制（$H,W \le 30$）。