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 sys
  import networkx as nx
  import numpy as np
  
  read = sys.stdin.buffer.read
  readline = sys.stdin.buffer.readline
  readlines = sys.stdin.buffer.readlines
  
  H, W = map(int, readline().split())
  S = np.frombuffer(read(), "S1").reshape(H, -1)[:, :W].astype("U1")
  
  INF = 1 << 32
  
  total_o = (S == "o").sum()
  G = nx.DiGraph()
  sink = "sink"
  G.add_node(sink, demand=total_o)
  for i in range(H):
      for j in range(W):
          if S[i, j] == "#":
              continue
          if S[i, j] == "o":
              G.add_node((i, j), demand=-1)
              G.add_edge((i, j), sink, capacity=1, weight=0)
          elif S[i, j] == ".":
              G.add_node((i, j), demand=0)
              G.add_edge((i, j), sink, capacity=1, weight=0)
          if i + 1 < H and S[i + 1, j] != "#":
              G.add_edge((i, j), (i + 1, j), capacity=INF, weight=-1)
          if j + 1 < W and S[i, j + 1] != "#":
              G.add_edge((i, j), (i, j + 1), capacity=INF, weight=-1)
  
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"}]