Score : 600 points
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:
.
: the square is empty.#
: an obstacle is placed on the square.o
: a piece is placed on the square.Yosupo repeats the following operation:
Yosupo wants to perform the operation as many times as possible. Find the maximum possible number of operations.
.
, #
and o
.o
is between 1 and 100, both inclusive.Input is given from Standard Input in the following format:
N M S_1 S_2 \vdots S_N
Print the maximum possible number of operations in a line.
3 3 o.. ... o.#
4
Yosupo can perform operations 4 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