配点 : $600$ 点

問題文

$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$ 個下，もしくは $1$ 個右のマスに移動させる． ただし，他の駒もしくは障害物のあるマスに駒を移動させる操作は禁止されている． もちろん，駒が盤面を飛び出すような操作も行えない．

yosupo くんは，できるだけ多くの回数操作をしたいです． 操作回数の最大値を求めてください．

制約

• $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$ 個以下．

入力

入力は以下の形式で標準入力から与えられる．

$N$ $M$

$S_1$

$S_2$

$\vdots$

$S_N$

出力

操作回数の最大値を一行に出力せよ．

3 3
o..
...
o.#

4

以下のように $4$ 回の操作を行えます．

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

9 10
.#....o#..
.#..#..##o
.....#o.##
.###.#o..o
#.#...##.#
..#..#.###
#o.....#..
....###..o
o.......o#

24