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: def solve(k):
      dp = [[0] * (h + 1) for i in range(h + 1)]
      for i in range(h):
          for diff in range(h - i):
              dp[i + 1][i + 1 + diff] = dp[i][i + diff] + (s[i + diff][k] == s[i][k + 1])
              dp[i + 1 + diff][i + 1] = dp[i + diff][i] + (s[i][k] == s[i + diff][k + 1])
  
      dq = [[INF] * (h + 1) for i in range(h + 1)]
      dq[0][0] = 0
      for i in range(h):
          dq[i + 1][0] = dq[i][0] + dp[h - i][h]
          dq[0][i + 1] = dq[0][i] + dp[h][h - i]
      for i in range(h):
          for j in range(h):
              dq[i + 1][j + 1] = min(
                  dq[i + 1][j] + dp[h - (i + 1)][h - j],
                  dq[i][j + 1] + dp[h - i][h - (j + 1)],
              )
  
      return dq[h][h]
  
  
  h, w = map(int, input().split())
  s = [input() for i in range(h)]
  INF = 10**5
  OFFSET = 500
  
  ans = 0
  for i in range(w - 1):
      ans += solve(i)
  
  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"}]