output_description: Print the minimum total cost to dismantle the object.
  
  * * *
input_description: The input is given from Standard Input in the following format:
  
      
      
      H W
      c_{1,1}c_{1,2}..c_{1,W}
      c_{2,1}c_{2,2}..c_{2,W}
      :
      c_{H,1}c_{H,2}..c_{H,W}
attempt: import itertools
  
  
  h, w = map(int, input().split())
  c = [list(map(ord, input())) for i in range(h)]
  c = list(itertools.chain.from_iterable(c))
  INF = 10**9
  h2 = (h + 1) * (h + 1)
  
  ans = 0
  dq = [0] * h2
  for wi in range(w - 1):
      for diff in range(h + 1):
          cnt1 = 0
          cnt2 = 0
          for i in range(h - diff):
              cnt1 += c[i * w + wi] == c[(i + diff) * w + wi + 1]
              cnt2 += c[(i + diff) * w + wi] == c[i * w + wi + 1]
          dq[diff * (h + 1)] = cnt1
          dq[diff] = cnt2
          for i in range(h - diff - 1):
              cnt1 -= c[(h - i - 1 - diff) * w + wi] == c[(h - i - 1) * w + wi + 1]
              dq[(i + 1 + diff) * (h + 1) + i + 1] = cnt1
              cnt2 -= c[(h - i - 1 - diff) * w + wi + 1] == c[(h - i - 1) * w + wi]
              dq[(i + 1) * (h + 1) + i + 1 + diff] = cnt2
  
      dp = [INF] * h2
      dp[0] = 0
      for i in range(h + 1):
          for j in range(h + 1):
              if i + 1 < h + 1:
                  dp[(i + 1) * (h + 1) + j] = min(
                      dp[i * (h + 1) + j] + dq[i * (h + 1) + j], dp[(i + 1) * (h + 1) + j]
                  )
              if j + 1 < h + 1:
                  dp[i * (h + 1) + j + 1] = min(
                      dp[i * (h + 1) + j] + dq[i * (h + 1) + j], dp[i * (h + 1) + j + 1]
                  )
      ans += dp[-1]
  
  print(ans)
  
problem_description: Statement
  
  Mr. Takahashi has in his room an art object with H rows and W columns, made up
  of H \times W blocks. Each block has a color represented by a lowercase
  English letter (`a`-`z`). The color of the block at the i-th row and j-th
  column is c_{i,j}.
  
  Mr. Takahashi would like to dismantle the object, finding it a bit kitschy for
  his tastes. The dismantling is processed by repeating the following operation:
  
    * Choose one of the W columns and push down that column one row. The block at the bottom of that column disappears.
  
  Each time the operation is performed, a cost is incurred. Since blocks of the
  same color have a property to draw each other together, the cost of the
  operation is the number of the pairs of blocks (p, q) such that:
  
    * The block p is in the selected column.
    * The two blocks p and q are horizontally adjacent (before pushing down the column).
    * The two blocks p and q have the same color.
  
  Mr. Takahashi dismantles the object by repeating the operation H \times W
  times to get rid of all the blocks. Compute the minimum total cost to
  dismantle the object.
samples: [{"input": "2 3\n    rrr\n    brg", "output": "2\n    \n\nFor example, the total cost of 2 can be achieved by performing the operation\nas follows and this is the minimum value.\n\n![ccb25ed6f1df9367829b68523e1deff4.png](https://atcoder.jp/img/code-\nfestival-2016-qualc/ccb25ed6f1df9367829b68523e1deff4.png)\n\n* * *"}, {"input": "6 3\n    xya\n    xya\n    ayz\n    ayz\n    xaz\n    xaz", "output": "0\n    \n\nThe total cost of 0 can be achieved by first pushing down all blocks of the\nmiddle column, then all of the left column, and all of the right column.\n\n* * *"}, {"input": "4 2\n    ay\n    xa\n    xy\n    ay", "output": "0\n    \n\nThe total cost of 0 can be achieved by the following operations:\n\n  * pushing down the right column one row;\n  * pushing down the left column one row;\n  * pushing down all of the right column;\n  * and pushing down all of the left column.\n\n* * *"}, {"input": "5 5\n    aaaaa\n    abbba\n    ababa\n    abbba\n    aaaaa", "output": "24\n    \n\n* * *"}, {"input": "7 10\n    xxxxxxxxxx\n    ccccxxffff\n    cxxcxxfxxx\n    cxxxxxffff\n    cxxcxxfxxx\n    ccccxxfxxx\n    xxxxxxxxxx", "output": "130"}]