지명

지명(toponym)은 도시, 마을, 강, 산 등에 붙는 이름이다. 몰도바 공화국에서는 서로 매우 비슷한 지명을 흔히 볼 수 있다. 예를 들어 Orhei와 Orheiul Vechi, 또는 Jora de Sus, Jora de Mijloc, Jora de Jos 등이 있다.

일반적으로 모든 지명은 문자 A, B, C, …, Z, a, b, c, …, z 와 공백 문자로 이루어진 문자열이다. 지명 안에서 공백 문자가 두 개 이상 연속해서 나타날 수는 없다. 또한 지명의 맨 앞이나 맨 뒤에 공백이 오지 않는다. 어떤 지명의 처음 $m$개 문자로 이루어진 부분 문자열을 길이 $m$의 접두사(prefix)라고 한다. 예를 들어 부분 문자열 Jora는 지명 Jora de Mijloc의 길이 $m = 4$인 접두사이다.

• 지명 집합 $T$의 유사도(level of similarity) $Ls(T)$는 $T$에 속한 지명들의 가장 긴 공통 접두사의 길이로 정의한다. 예를 들어 지명 집합 $T$ = {Jora de Sus, Jora de Mijloc, Jora de Jos}에 대해 $Ls(T) = 8$이다.
• 지명 집합 $T$의 복잡도(level of complexity) $Lc(T)$는 다음과 같이 정의한다. $$Lc(T) = Ls(T) \times k\text{,}$$ 여기서 $k$는 $T$에 속한 지명의 개수이다.

예를 들어 지명 집합 $T$ = {Jora de Sus, Jora de Mijloc, Jora de Jos}에 대해 $Lc(T) = 24$이다.

주어진 지명 집합 $S$에 대해, 복잡도 $Lc(T)$가 최대가 되는 부분집합 $T$ ($T \subseteq S$)를 찾아 그 최대 복잡도를 구하는 프로그램을 작성하라.

첫째 줄에 집합 $S$에 속한 지명의 개수 $n$이 주어진다. 다음 $n$개의 줄에 각각 하나의 지명이 주어진다. 각 지명은 문자 A, B, C, …, Z, a, b, c, …, z 와 공백으로 이루어진 문자열이다.

최대 복잡도 $Lc(T)$를 나타내는 정수 하나를 한 줄에 출력한다.

• $2 \le n \le 1000000$
• 각 지명의 길이는 20000자를 넘지 않는다.
• 입력 전체의 크기는 10MB를 넘지 않는다.