你是 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