C - Moving Pieces 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 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

出力

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

入力例 1

3 3
o..
...
o.#

出力例 1

4

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

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

入力例 2

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

出力例 2

24

Score : 600 points

Problem Statement

There is a board with N rows and M columns. The information of this board is represented by N strings S_1,S_2,\ldots,S_N. Specifically, the state of the square at the i-th row from the top and the j-th column from the left is represented as follows:

  • S_{i,j}=. : the square is empty.
  • S_{i,j}=# : an obstacle is placed on the square.
  • S_{i,j}=o : a piece is placed on the square.

Yosupo repeats the following operation:

  • Choose a piece and move it to its right adjecent square or its down adjacent square. Moving a piece to squares with another piece or an obstacle is prohibited. Moving a piece out of the board is also prohibited.

Yosupo wants to perform the operation as many times as possible. Find the maximum possible number of operations.

Constraints

  • 1 \leq N \leq 50
  • 1 \leq M \leq 50
  • S_i is a string of length M consisting of ., # and o.
  • 1 \leq ( the number of pieces )\leq 100. In other words, the number of pairs (i, j) that satisfy S_{i,j}=o is between 1 and 100, both inclusive.

Input

Input is given from Standard Input in the following format:

N M
S_1
S_2
\vdots
S_N

Output

Print the maximum possible number of operations in a line.

Sample Input 1

3 3
o..
...
o.#

Sample Output 1

4

Yosupo can perform operations 4 times as follows:

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

Sample Input 2

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

Sample Output 2

24