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())
  
  S = [list(input()) for _ in range(n)]
  G = nx.DiGraph()
  
  start = (n, m)
  cnt = 0
  goal = (n, m + 1)
  
  for i in range(n):
      for j in range(n):
          if S[i][j] != "#":
              if S[i][j] == "o":
                  cnt += 1
                  G.add_edge(start, (i, j), capacity=1)
              if i + 1 < n:
                  if S[i + 1][j] != "#":
                      G.add_edge((i, j), (i + 1, j), weight=-1)
              if j + 1 < m:
                  if S[i][j + 1] != "#":
                      G.add_edge((i, j), (i, j + 1), weight=-1)
              G.add_edge((i, j), goal, capacity=1)
  # G.add_node(start, demand=cnt)
  # G.add_node(goal, demand=-cnt)
  mincostflow = nx.max_flow_min_cost(G, start, goal)
  ans = nx.cost_of_flow(G, mincostflow)
  print(abs(ans))
  
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"}]