この問題は「2023秋祭」のアーカイブです。2023 Akisai-F

H問題 - Gomamayo (hard)

実行時間制限: 2 sec / メモリ制限: 1024 MB

問題文

\(N\)個の文字列\(S_i\)が与えられます。あなたは\(S_i\)のうちいくつかを次の条件を満たすように連結せさ、新しい文字列\(T\)を作りたいです。

条件

• 文字列\(A\)と文字列\(B\)は、\(A\)の末尾と\(B\)の先頭の文字が完全に一致するならば文字列\(A\)と文字列\(B\)を使用して\(AB\)の順で連結することができる。 すなわち、\(AB\)は\(A\)と\(B\)の境界を等しくする狭義ゴママヨ文字列(C問題参照)となる。
• \(S_i\)は1回のみ使用することができる。

考えられる新しい文字列\(T\)のうち最長となるものの長さを求めてください。

制約

• \(2 \leq N \leq 16\)
• \(1 \leq |S| \leq 100\)
• \(N\)は整数として与えられる。
• \(S_i\)は大小英文字として与えられる。 ## 入力

N
S_1 S_2 ... S_N

出力

考えられる最長の新しい文字列\(T\)の長さを1行で出力せよ。

入力例1

6
abc bba cbb ace bad cge

出力例1

12

入力例2

6
a a a b b b

出力例2

3

1文字の先頭と末尾は等しいので、aaaやbbbと連結することができます。それぞれの文字列は１回以下使用できることに注意してください。 aaaと連結してもbbbと連結しても長さは3で、最長です。

入力例3

1
a

出力例3

1