リファレンス文字列
小文字のラテン文字からなる
n 個の文字列が与えられているとします。ここでは、小文字のラテン文字と文字 # から成る文字列 s を リファレンス文字列 と呼びます。具体的には、与えられたリストの各文字列について、s のあるインデックス i（このとき ≠ #）を選び、その i から次に現れる # まで（ただし # 自体は含まない）の部分文字列を取り出すと、リスト中の文字列のいずれかと一致するようになっているものを指します。なお、リファレンス文字列は必ず最後に # を付けて終わる必要があります。このリストに対して上記の条件を満たす最短のリファレンス文字列の長さを求めるプログラムを作成してください。
入力
最初の行に、リストの文字列数を表す整数
n (1 ≤ n ≤ 100 000) が与えられます。続く
n 行には、各行に小文字のラテン文字からなる文字列が1つずつ与えられます。それぞれの文字列の長さは 最大で 10 です。出力
条件を満たす 最短のリファレンス文字列 の長さを表す整数を1つ出力してください。
Examples
Input | Output |
6
found
profound
ground
round
wound
und | 22 |
3
ab
bc
cd | 9 |
Explanation
- Example 1: one of the shortest reference strings is the string ‘
ground#profound#wound#’.
- Example 2: one of the shortest reference strings is the string ‘
ab#bc#cd#’.
Constraints
Time limit: 5 seconds
Memory limit: 512 MB
Output limit: 1 MB