/ 
Time Limit: 2 sec / Memory Limit: 256 MB
KUPCに参加しているあなたは、不運にもコーディング中にモンスターの集団に妨害されてしまった。 優秀なプログラマーであるあなたは、モンスターに対して適切な文字列で攻撃して退治しなければならないのであった。
モンスターは N 体いる。各モンスターにはそれぞれ弱点があり、i 番目 ( i=1,….,N )のモンスターの弱点は文字列S_iで表される。 i 番目のモンスターが文字列 T で攻撃されたとき、T が S_i の部分文字列であるならばそのモンスターは |T| のダメージを受ける。 部分文字列でない場合はダメージは 0 になる。
あなたは文字列 T を一つ決めて、N 体のモンスターに T で一度ずつ攻撃する。
この時、N 体のモンスターに与えるダメージの総和を最大にするような T を求め、ダメージの総和を出力せよ。
ただし、ダメージが 0 のモンスターがいても良い。
文字列 x について、|x| は x の長さを意味する。
文字列 x と文字列 y について、
x = y_i y_{i+1} … y_{i+l-1}
(1 \leq i \leq |y|, 0 \leq l \leq |y|-i+1)
であるとき、x は y の部分文字列であると言う。
ただし y_i (i = 1,…,|y|) は、
y の i 番目の文字を意味する。
入力形式
入力は以下の形式で与えられる。
N S_1 … S_N
一行目にモンスターの数を表す整数 N があたえられる。
続く N 行はそれぞれモンスターの弱点を表す文字列 S_i ( i=1,…,N)が与えられる。
出力形式
モンスターに与えるダメージの総和の最大値を出力せよ。
制約
- 1 \leq N \leq 10^5
- S_i は英小文字 ('a',…,'z') のみからなる、空でない文字列である。
- |S_1|+|S_2|+…+|S_N| \leq 10^5
この問題の判定には、40点分のテストケースのグループが設定されている。このグループに含まれるテストケースは上記の制約に加えて下記の制約も満たす。
- N \leq 50
入出力例
入力例1
3 aab ab ac
出力例1
4
文字列"a"で攻撃すると 1, 2, 3 番目のモンスターにそれぞれ 1 ダメージを与え、ダメージの総和は 3 である。
文字列"ab"で攻撃すると 1, 2 番目のモンスターにそれぞれ 2 ダメージを与え、ダメージの総和は 4 である。
この時、ダメージの総和は最大になる。
入力例2
2 abcde cd
出力例2
5