Friction

高橋君有一个$h * w$的艺术品，艺术品的每一块都有一个小写字母表示颜色。 高橋君想把这个艺术品拆掉，他采取这样的方式： 选取一列并把这一列向下推一格，这样这一列最下边的颜色会消失。 但是这会产生代价。产生的代价是选择的这一列中，与相邻格子颜色相同的格子数。确切来说，当有一对格子$(p,q)$满足 - $p$在所选的这一列 - $p,q$ 水平相邻 - $p,q$颜色相同 这对格子会产生$1$的代价。 请计算高橋君把这个艺术品完全拆除所需要的最小代价。 范围： $1 \leq h \leq 300$ $2 \leq w \leq 300$

[problemUrl]: https://atcoder.jp/contests/code-festival-2016-qualc/tasks/codefestival_2016_qualC_d 高橋君の部屋には縦 $ H $ 行、横 $ W $ 列、 $ H\ \times\ W $ 個のブロックからなるオブジェがあります。 各ブロックには色がついています。色は英小文字(`a`-`z`) で表されます。上から $ i $ 個目、左から $ j $ 個目のブロックの色は $ c_{i,j} $ です。 あまり見栄えが良くないため高橋君はこのオブジェを解体しようとしています。解体作業は以下の操作の繰り返しになります。 - $ W $ 個の列のうち一つを選び、その列を一段沈める。その列の一番下にあったブロックは消滅する。 同じ色のブロックは引き寄せ合う力を持つため、この操作にかかるコストは、「選んだ列のブロックと(操作前に)横に隣り合っているブロックで、色が同じもの の個数」になります。 高橋君はこの作業を $ H\ \times\ W $ 回行うことで全てのブロックを消滅させオブジェを解体します。操作する列の順番をうまく選ぶことによって、解体にかかるコストの総和を最小化してください。

入力は以下の形式で標準入力から与えられる。 > $ 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} $

解体にかかるコストの総和の最小値を出力せよ。

2 3
rrr
brg

2

6 3
xya
xya
ayz
ayz
xaz
xaz

0

4 2
ay
xa
xy
ay

0

5 5
aaaaa
abbba
ababa
abbba
aaaaa

24

7 10
xxxxxxxxxx
ccccxxffff
cxxcxxfxxx
cxxxxxffff
cxxcxxfxxx
ccccxxfxxx
xxxxxxxxxx

130

### 制約 - $ 1≦H≦300 $ - $ 2≦W≦300 $ - $ c_{i,j} $ は英小文字(`a`-`z`) ### 部分点 - $ W=3 $ を満たすデータセットに正解すると、$ 300 $ 点が与えられる。 ### Sample Explanation 1 例えば下図のような順で操作するとコストの総和は $ 2 $ に出来て、これが最小値です。 !\[c116dab4c0a2f42759c6476d95330a37.png\](https://atcoder.jp/img/code-festival-2016-qualc/c116dab4c0a2f42759c6476d95330a37.png) ### Sample Explanation 2 はじめに真ん中の列を全て沈め、次に左の列を全て沈め、最後に右の列を全て沈めることでコスト$ 0 $を達成できます。 ### Sample Explanation 3 右の列を一段沈める→左の列を一段沈める→右の段を全て沈める→左の段を全て沈める とすることでコスト$ 0 $にすることが可能です。