時間制限 : sec, メモリ制限 : KB
Japanese

C: Cyclic String

問題文

文字列 $S = s_0 s_1 \ldots s_{n-1}$ が文字列 $T = t_0 t_1 \ldots t_{m-1}$ に巡回的に含まれるとは、 ある $k$ があって、全ての $i$ $(0 \le i \lt n)$ について $s_i = t_{(i+k) \bmod m}$ が成立する事を言います。

$N$ 個の文字列 $S_1, \dots, S_N$ が与えられます。 以下の条件を満たす文字列の集合 $\{C_1, \dots, C_k\}$ を考えます($k$ は任意):

  • 各$i$ $(1 \leq i \leq N)$について、$S_i$は少なくとも1つの$C_j$に巡回的に含まれる。$(1 \leq j \leq k)$

$|C_1| + |C_2| + \cdots + |C_k|$の最小値を求めてください。

制約

  • $1 \leq N \leq 100$
  • $1 \leq |S_i| \leq 1000$
  • $S_i$ の各文字は英小文字または英大文字である
  • 任意の$i,j$ $(i \ne j)$について、$S_i$ は $S_j$ の連続する部分文字列ではない

入力

入力は標準入力から以下の形式で与えられます。

$N$
$S_1$
$S_2$
$\vdots$
$S_N$

出力

答えを一行で出力してください。

入出力例

入力例1

3
dea
xxx
abcd

出力例1

6

例えば、文字列の集合 {"abcde", "x"} は問題文の条件を満たし、文字列の長さの合計は $6$ です。

入力例2

1
xy

出力例2

2

入力例3

3
AAaaBB
aaBBAA
AaB

出力例3

9