「CZYZOI 2017.04.24 JZ 03.08 B」 押韵

内存限制: 256 MiB 时间限制: 1000 ms
标准输入输出

题目描述

小A非常喜欢所有押韵的东西,他认为两个单词押韵当且仅当他们的公共后缀的长度和两个单词中最长的单词的长度相等,或者是最长的单词的长度减一。

也就是说 LCS(A,B)max(A,B)1LCS(A,B)\ge max(|A|,|B|)-1

有一天,小A读了一个有N个单词的小故事,

他想知道,如果挑选一些故事里出现的单词组成一个新的单词序列,能组成的最长的满足以下条件的单词序列的长度是多少:

单词序列中任意相邻的两个单词都押韵。(每个单词最多只能用一次)

输入格式

第一行包含一个正整数 N(1N500000)N(1\le N\le500000) ,表示单词的个数。

接下来 NN 行,每行一个由英文小写字母构成的单词,表示原故事里的单词。

输入保证所有单词都不一样,并且他们的总长度不超过 3,000,0003,000,000

输出格式

输出满足条件的最长单词序列的长度。

样例

输入样例1

4
honi
toni
oni
ovi

输出样例1

3

输入样例2

5
k
ask
psk
krafna
sk

输出样例2

4

输入样例3

5
pas
kompas
stas
s
nemarime

输出样例3

1

数据范围与提示

30%30\% 的数据,有 N18N\le 18