题目描述

$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 くんは，できるだけ多くの回数操作をしたいです． 操作回数の最大値を求めてください．

输入格式

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

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

输出格式

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

题目大意

有$N$ 行 $M$ 列的表格，是 $N$ 个长度为 $M$ 的字符串 $S_1,S_2,\ldots,S_N$ 组成。

• $S_{i,j}=$. ：空格子。
• $S_{i,j}=$# ：格子中有障碍物。
• $S_{i,j}=$o ：这个格子里放着 $1$ 个棋子。

王尨接下来会向下或者向右移动一个棋子。
求出王尨可操作次数的最大值。

3 3
o..
...
o.#

4

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

24

提示

制約

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

Sample Explanation 1

以下のように $4$ 回の操作を行えます． o.. .o. ..o ... ... ... -> ... -> ... -> ..o -> ..o o.# o.# o.# o.# .o#