AT_acl1_c.Moving Pieces

有一个由 $N$ 行 $M$ 列组成的棋盘。该棋盘的信息由 $N$ 个字符串 $S_1,S_2,\ldots,S_N$ 表示。具体来说，从上到下第 $i$ 行，从左到右第 $j$ 列的格子的状态如下所示：

• $S_{i,j} = $. ：该格子为空。
• $S_{i,j} = $# ：该格子上有障碍物。
• $S_{i,j} = $o ：该格子上有 $1$ 个棋子。

yosupo 君将不断重复以下操作：

• 选择一个棋子，将其移动到下方 $1$ 格或右方 $1$ 格。 但不能将棋子移动到有其他棋子或障碍物的格子上。 当然，也不能将棋子移出棋盘。

yosupo 君想要尽可能多地进行操作。请你求出操作次数的最大值。

输入通过标准输入按以下格式给出。

$N$ $M$
$S_1$
$S_2$
$\vdots$
$S_N$

请输出操作次数的最大值。

限制条件

• $1 \leq N \leq 50$
• $1 \leq M \leq 50$
• $S_i$ 是由 ., #, o 组成的长度为 $M$ 的字符串。
• $1 \leq$（棋子的个数）$\leq 100$。也就是说，满足 $S_{i,j} = $o 的 $(i,j)$ 的个数在 $1$ 到 $100$ 之间。

样例解释 1

可以按如下方式进行 $4$ 次操作。

o..
.o.
..o
...
...
...
-> ...
-> ...
-> ..o
-> ..o
o.#
o.#
o.#
o.#
.o#

由 ChatGPT 4.1 翻译