output_description: Print the maximum possible number of operations in a line.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N M
      S_1
      S_2
      \vdots
      S_N
attempt: import networkx as nx
  
  n, m = map(int, input().split())
  board = [input() for _ in range(n)]
  k = 0
  for i in range(n):
      for j in range(m):
          if board[i][j] == "o":
              k += 1
  INF = 10**9
  g = nx.DiGraph()
  g.add_node(0, demand=k)
  for i in range(n):
      for j in range(m):
          if board[i][j] == "#":
              continue
          if board[i][j] == "o":
              g.add_node((i, j), demand=-1)
              g.add_edge((i, j), 0, capacity=1, weight=0)
          elif board[i][j] == ".":
              g.add_node((i, j), demand=0)
              g.add_edge((i, j), 0, capacity=1, weight=0)
          if i + 1 < n and board[i + 1][j] != "#":
              g.add_edge((i, j), (i + 1, j), weight=-1, capacity=INF)
          if j + 1 < m and board[i][j + 1] != "#":
              g.add_edge((i, j), (i, j + 1), weight=-1, capacity=INF)
  flow = nx.min_cost_flow(g)
  result = sum(v * g[k1][k2]["weight"] for k1, dc in flow.items() for k2, v in dc.items())
  print(-result)
  
problem_description: 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.
samples: [{"input": "3 3\n    o..\n    ...\n    o.#", "output": "4\n    \n\nYosupo can perform operations 4 times as follows:\n\n    \n    \n    o..      .o.      ..o      ...      ...\n    ...  ->  ...  ->  ...  ->  ..o  ->  ..o\n    o.#      o.#      o.#      o.#      .o#\n    \n\n* * *"}, {"input": "9 10\n    .#....o#..\n    .#..#..##o\n    .....#o.##\n    .###.#o..o\n    #.#...##.#\n    ..#..#.###\n    #o.....#..\n    ....###..o\n    o.......o#", "output": "24"}]