atcoder#ACL1C. Moving Pieces

Moving Pieces

Score : 600600 points

Problem Statement

There is a board with NN rows and MM columns. The information of this board is represented by NN strings S1,S2,,SNS_1,S_2,\ldots,S_N. Specifically, the state of the square at the ii-th row from the top and the jj-th column from the left is represented as follows:

  • Si,j=S_{i,j}=. : the square is empty.
  • Si,j=S_{i,j}=# : an obstacle is placed on the square.
  • Si,j=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

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

Input

Input is given from Standard Input in the following format:

NN MM

S1S_1

S2S_2

\vdots

SNS_N

Output

Print the maximum possible number of operations in a line.

3 3
o..
...
o.#
4

Yosupo can perform operations 44 times as follows:

o..      .o.      ..o      ...      ...
...  ->  ...  ->  ...  ->  ..o  ->  ..o
o.#      o.#      o.#      o.#      .o#
9 10
.#....o#..
.#..#..##o
.....#o.##
.###.#o..o
#.#...##.#
..#..#.###
#o.....#..
....###..o
o.......o#
24