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
  import sys
  
  input = sys.stdin.readline
  sys.setrecursionlimit(10**9)
  
  
  def solve():
      INF = float("inf")
  
      def max2(x, y):
          return x if x >= y else y
  
      N, M = map(int, input().split())
      Sss = ["#" * (M + 2)] + ["#" + input() + "#" for _ in range(N)] + ["#" * (M + 2)]
  
      poss = []
      for i in range(1, N + 1):
          for j in range(1, M + 1):
              if Sss[i][j] == "o":
                  poss.append((i, j))
  
      numA = len(poss)
  
      def f(x, y):
          anss = []
          dp = [-INF] * (M + 2)
          for i in range(1, N + 1):
              dp2 = [-INF] * (M + 2)
              for j in range(1, M + 1):
                  if Sss[i][j] == "#":
                      continue
                  if i == x and j == y:
                      dp2[j] = 0
                  else:
                      dp2[j] = max2(dp[j], dp2[j - 1]) + 1
              dp = dp2
              anss.append(dp[1:-1])
          return anss
  
      # for x, y in poss:
      #     f(x, y)
      #     print()
  
      s, t = N * M + numA, N * M + numA + 1
      G = nx.DiGraph()
      G.add_node(s, demand=-numA)
      G.add_node(t, demand=numA)
      for i in range(N):
          for j in range(M):
              k = i * M + j
              G.add_node(k)
              G.add_edge(k, t, weight=0, capacity=1)
  
      KK = 10**6
      for iPos, (x, y) in enumerate(poss, start=N * M):
          G.add_node(iPos)
          G.add_edge(s, iPos, weight=0, capacity=1)
          dp = f(x, y)
          for i in range(N):
              for j in range(M):
                  if dp[i][j] != -INF:
                      k = i * M + j
                      wt = KK - dp[i][j]
                      G.add_edge(iPos, k, weight=wt, capacity=1)
  
      C = nx.min_cost_flow_cost(G)
      ans = KK * numA - C
      print(ans)
  
  
  solve()
  
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"}]