题目描述

高桥先生的房间里有一个艺术品，它由 $H$ 行和 $W$ 列组成，总共有 $H \times W$ 个方块。每个方块由一个小写英文字母（a-z）表示。第 $i$ 行和第 $j$ 列的方块颜色为 $c_{i,j}$。

高桥先生希望拆卸这个艺术品，因为他认为它有点俗气。拆卸是通过重复以下操作进行的：

• 选择一列中的一个方块，并将该列向下推移一行。该列底部的方块会消失。

每次执行该操作都会产生一定的代价。由于相同颜色的方块具有相互吸引的特性，操作的代价是满足以下条件的方块对 $(p, q)$ 的数量：

• 方块 $p$ 在被选中的列中。
• 在推动列之前，方块 $p$ 和 $q$ 是水平相邻的。
• 方块 $p$ 和 $q$ 具有相同的颜色。

高桥先生通过重复执行 $H \times W$ 次操作来拆除艺术品上的所有方块。计算拆卸艺术品的最小总代价。

约束条件

• $1 ≤ H ≤ 300$
• $2 ≤ W ≤ 300$
• 所有字符 $c_{i,j}$ 都是小写英文字母（a-z）。

输入

从标准输入读入数据，输入格式如下：

$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