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 sys
  
  input = lambda: sys.stdin.readline().rstrip()
  sys.setrecursionlimit(max(1000, 10**9))
  write = lambda x: sys.stdout.write(x + "\n")
  
  
  h, w = list(map(int, input().split()))
  c = [None] * h
  for i in range(h):
      c[i] = input()
  # def sub(i):
  #     c0 = c[i]
  #     c1 = c[i+1]
  #     dp = [[None]*(h+1) for _ in range(h+1)]
  #     for i in range(h+1):
  #         dp[i][0] = 0
  #         dp[0][i] = 0
  #     val = [None]*(2*h+1) # c0がc1よりi-h高いときの衝突数の累積和
  #     for i in range(h):
  #         # c1がh, c0がi
  #         l = []
  #         v = 0
  #         for j in range(i):
  #             if c1[h-i+j]==c0[j]:
  #                 v += 1
  #             l.append(v)
  #         val[i] = l
  #     for i in range(h, -1, -1):
  #         # c0がh, c1がi
  #         l = []
  #         v = 0
  #         for j in range(i):
  #             if c0[h-i+j]==c1[j]:
  #                 v += 1
  #             l.append(v)
  #         val[h+(h-i)] = l
  
  #     for i in range(1, h+1):
  #         for j in range(1, h+1):
  #             dp[i][j] = min(dp[i+1][j]+val[(i+1)-j+h][i], dp[i][j+1]+val[i-(j+1)+h][i-1])
  #     return dp[h][h]
  ans = 0
  for i in range(w - 1):
      c0 = [c[j][i] for j in range(h)]
      c1 = [c[j][i + 1] for j in range(h)]
      dp = [[None] * (h + 1) for _ in range(h + 1)]
      for i in range(h + 1):
          dp[i][0] = 0
          dp[0][i] = 0
      val = [None] * (2 * h + 1)  # c0がc1よりi-h高いときの衝突数の累積和
      for i in range(h):
          # c1がh, c0がi
          l = []
          v = 0
          for j in range(i):
              if c1[h - i + j] == c0[j]:
                  v += 1
              l.append(v)
          val[i] = l
      for i in range(h, -1, -1):
          # c0がh, c1がi
          l = []
          v = 0
          for j in range(i):
              if c0[h - i + j] == c1[j]:
                  v += 1
              l.append(v)
          val[h + (h - i)] = l
  
      for i in range(1, h + 1):
          for j in range(1, h + 1):
              cost = val[(i) - j + h][min(i, j) - 1]
              dp[i][j] = min(dp[i - 1][j] + cost, dp[i][j - 1] + cost)
      ans += dp[h][h]
  #     return dp[h][h]
  
  #     ans += sub(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"}]