問題文

ナダ地方には $N$ 種類のサルが生息しています。
あなたは DNA 配列を用いてナダ地方のサルの系統樹を作成することになりました。
系統樹は生物の種間関係を示す全二分木で、葉ノードが生物に対応し、内部ノードが分岐点に対応しています。
DNA 配列は A, T, G, C からなる文字列で表され、サル種 $1$ からサル種 $N$ のそれぞれについて、長さ $L$ の DNA 配列 $G_1$ から $G_N$ が与えられます。
系統樹の不正確性の指標として「系統樹のコスト」が以下に説明されるように定義されます。

----
<系統樹のコスト>
まず次のように、$2$ 種類のサルの DNA 距離 ${\rm D}(X,\ Y)$ を定義します：相異なる $2$ 種類のサル種 $X, Y$ の DNA 配列 $G_X,\ G_Y$ について、$G_X$ と $G_Y$ のそれぞれ左から $i$ 番目 $(1\leq i\leq L)$ の文字が一致しなかった数(ハミング距離)をその $2$ 種の DNA 距離と定義し、${\rm D}(X,\ Y)$ と表すことにします。
例えば、$G_X,\ G_Y$ がそれぞれ ACGTTA, ACCTGA であるとき、左から $3, 5$ 番目の文字が異なっているため、${\rm D}(X, Y) = 2$ です。
次に、分岐点のコストを次のように定義します：分岐点の片側の二分木に属する種のうち一つを種 $A$ 、もう片側の二分木に属する種のうち一つを種 $B$ としたとき、${\rm D}(A,\ B)$ の最小値をその分岐点のコストとします。
系統樹の各分岐点のコストの和を「系統樹のコスト」とします。
----

あなたはなるべくコストの低い系統樹を作りたいです。$N$ 種類のサルの系統樹のコストとして考えられる最小の値を出力してください。

入力

$N\ \ \ L$
$G_1$
$G_2$
$\ \vdots$
$G_N$

$N,\ L$ は整数
$2\leq N\leq 1000$
$1\leq L\leq 50$
$G_i$ は A, T, G, C から成る長さ $L$ の文字列 $(1 \leq i \leq N)$

出力

答えを$1$行に出力してください。
最後に改行してください。

サンプル

3 4
AAAA
AGGA
AGGT

3

4 7
TCAAGCT
TAACGCC
ACACGTT
ACGACTC

10

出典

灘校75回生中学卒業記念コンテスト: NADA DNA
writer: tetanura
tester: Mitarushi
HackerRankの規約に基づいて移植しております。一部改変したところがあります。