問題文

高橋君の部屋には縦 $H$ 行、横 $W$ 列、 $H \\times W$ 個のブロックからなるオブジェがあります。 各ブロックには色がついています。色は英小文字(a-z) で表されます。上から $i$ 個目、左から $j$ 個目のブロックの色は $c_{i,j}$ です。

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

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

同じ色のブロックは引き寄せ合う力を持つため、この操作にかかるコストは、「選んだ列のブロックと(操作前に)横に隣り合っているブロックで、色が同じもの の個数」になります。

高橋君はこの作業を $H \\times 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$ に出来て、これが最小値です。

---

入力例 2

6 3
xya
xya
ayz
ayz
xaz
xaz

出力例 2

0

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

---

入力例 3

4 2
ay
xa
xy
ay

出力例 3

0

右の列を一段沈める→左の列を一段沈める→右の段を全て沈める→左の段を全て沈める とすることでコスト$0$にすることが可能です。

---

入力例 4

5 5
aaaaa
abbba
ababa
abbba
aaaaa

出力例 4

24

---

入力例 5

7 10
xxxxxxxxxx
ccccxxffff
cxxcxxfxxx
cxxxxxffff
cxxcxxfxxx
ccccxxfxxx
xxxxxxxxxx

出力例 5

130