Problem Description

Takahashi's room has an object consisting of $ H $ rows and $ W $ columns of blocks, totaling $H \times W$ blocks. Each block is colored, represented by lowercase English letters (a-z). The color of the block at the $ i $-th row from the top and the $ j $-th column from the left is $ c_{i,j} $.

Takahashi wants to dismantle this object because it doesn't look very presentable. The dismantling process involves repeating the following operation:

• Choose one of the $ W $ columns and sink that column by one level. The block at the bottom of that column will disappear.

Blocks of the same color have a force that attracts each other. The cost of this operation is the number of blocks in the chosen column that are adjacent (before the operation) to blocks of the same color.

Takahashi will perform this operation $H \times W$ times to make all blocks disappear and dismantle the object. By choosing the order of columns to operate on wisely, minimize the total cost of dismantling.

Input Format

The input is given from the 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 Format

Output the minimum total cost of dismantling.

Sample Input and Output

Sample Input #1

2 3
rrr
brg

Sample Output #1

2

Sample Input #2

6 3
xya
xya
ayz
ayz
xaz
xaz

Sample Output #2

0

Sample Input #3

4 2
ay
xa
xy
ay

Sample Output #3

0

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

Notes/Hints

Constraints

• $1 \leq H \leq 300$
• $2 \leq W \leq 300$
• $ c_{i,j} $ is a lowercase English letter (a-z)

Partial Points

• Correctly solving the dataset where $ W = 3 $ will award $ 300 $ points.

Sample Explanation 1

For example, operating in the order shown in the figure below will result in a total cost of $ 2 $, which is the minimum value.

Sample Explanation 2

Starting by sinking all blocks in the middle column, then all blocks in the left column, and finally all blocks in the right column achieves a cost of $ 0 $.

Sample Explanation 3

Sinking one level of the right column → sinking one level of the left column → sinking all levels of the right column → sinking all levels of the left column can achieve a cost of $ 0 $.

见题面 Input 部分

见题面 Output 部分