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 = sys.stdin.readline
  sys.setrecursionlimit(10 ** 7)
  
  import numpy as np
  
  """
  それぞれの隣接2列ごとに、可能な摩擦の最小値を実現する → 小問題に分割。
  """
  
  buffer = sys.stdin.buffer
  H,W = map(int,buffer.readline().split())
  C = np.frombuffer(buffer.read(),dtype='S1').reshape(H,-1)[:,:W].T
  
  dp_1 = np.zeros((W-1,H+H+1,H+1),dtype=np.int64)
  for r in range(H):
      dp_1[:,r+2:r+H+2,r+1] = (C[:-1] == C[1:,r][:,None])
  
  (C[:-1][:,:] == C[1:][:,r][])
  
  INF = 10**18
  # R-L+H -> min cost
  dp = np.full((W-1,H+H+1),INF,dtype=np.int64)
  dp[:,H] = 0
  for n in range(1,H+H+1):
      # n個目を置く
      prev = dp
      dp = np.full((W-1,H+H+1),INF,dtype=np.int64)
      dp[:,1:] = np.minimum(dp[:,1:],prev[:,:-1])
      dp[:,:-1] = np.minimum(dp[:,:-1],prev[:,1:])
      dp += dp_1[:,:,n]
  answer = dp[:,H].sum()
  print(answer)
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"}]