# CODE FESTIVAL 2016 qual C

## D - Friction

Time limit時間制限 : 2sec / Memory limitメモリ制限 : 512MB

### 問題文

あまり見栄えが良くないため高橋君はこのオブジェを解体しようとしています。解体作業は以下の操作の繰り返しになります。

• W 個の列のうち一つを選び、その列を一段沈める。その列の一番下にあったブロックは消滅する。

### 制約

• 1≦H≦300
• 2≦W≦300
• c_{i,j} は英小文字(a-z)

### 部分点

• W=3 を満たすデータセットに正解すると、300 点が与えられる。

### 入力

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}


### 入力例 1

2 3
rrr
brg


### 出力例 1

2


### 入力例 2

6 3
xya
xya
ayz
ayz
xaz
xaz


### 出力例 2

0


はじめに真ん中の列を全て沈め、次に左の列を全て沈め、最後に右の列を全て沈めることでコスト0を達成できます。

### 入力例 3

4 2
ay
xa
xy
ay


### 出力例 3

0


### 入力例 4

5 5
aaaaa
abbba
ababa
abbba
aaaaa


### 出力例 4

24


### 入力例 5

7 10
xxxxxxxxxx
ccccxxffff
cxxcxxfxxx
cxxxxxffff
cxxcxxfxxx
ccccxxfxxx
xxxxxxxxxx


### 出力例 5

130


Score : 800 points

### Problem 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.

### Constraints

• 1 ≤ H ≤ 300
• 2 ≤ W ≤ 300
• All characters c_{i,j} are lowercase English letters (a-z).

### Partial Score

• In test cases worth 300 points, W = 3.

### Input

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}


### Output

Print the minimum total cost to dismantle the object.

### Sample Input 1

2 3
rrr
brg


### Sample Output 1

2


For example, the total cost of 2 can be achieved by performing the operation as follows and this is the minimum value.

### Sample Input 2

6 3
xya
xya
ayz
ayz
xaz
xaz


### Sample Output 2

0


The total cost of 0 can be achieved by first pushing down all blocks of the middle column, then all of the left column, and all of the right column.

### Sample Input 3

4 2
ay
xa
xy
ay


### Sample Output 3

0


The total cost of 0 can be achieved by the following operations:

• pushing down the right column one row;
• pushing down the left column one row;
• pushing down all of the right column;
• and pushing down all of the left column.

### Sample Input 4

5 5
aaaaa
abbba
ababa
abbba
aaaaa


### Sample Output 4

24


### Sample Input 5

7 10
xxxxxxxxxx
ccccxxffff
cxxcxxfxxx
cxxxxxffff
cxxcxxfxxx
ccccxxfxxx
xxxxxxxxxx


### Sample Output 5

130