시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 3 0 0 0.000%

문제

A toponym is the name given to a city, village, river, mountain etc. Very often, in the Republic of Moldova, one can find toponyms which are very similar. For example, Orhei and Orheiul Vechi; Jora de Sus, Jora de Mijloc and Jora de Jos.

As a rule, every toponym represents a sequence consisting of the characters A, B, C, ..., Z, a, b, c, ..., z and blank character. In toponyms there can not appear sequences of two or more consecutive blanks. Toponyms have no leading or trailing blanks. The subsequences consisting of the first $m$ characters of the toponym is called a prefix of length $m$. For example, the subsequence Jora, is a prefix of length $m = 4$ of the toponym Jora de Mijloc.

  • Level of similarity $Ls(T)$ of a set $T$ of toponyms is defined as the length of the longest common prefix of the toponyms from $T$. For example, for the set of toponyms $T$ = {Jora de Sus, Jora de Mijloc, Jora de Jos}, the level of similarity $Ls(T) = 8$.
  • Level of complexity $Lc(T)$ of a set $T$ of toponyms is defined as $$Lc(T) = Ls(T) \times k\text{,}$$ where $k$ is the number of toponyms in $T$.

For example, for the set of toponyms $T$ = {Jora de Sus, Jora de Mijloc, Jora de Jos}, the level of complexity $Lc(T) = 24$.

Write a program which, for a given set of toponyms $S$, find the subset $T$, $T \subseteq S$, with the maximal level of complexity.

입력

The input contains on the first line an integer $n$ - number of toponyms in $S$. Each of the next $n $lines of the input file contains a toponym. Each toponym is a string of characters A, B, C, …, Z, a, b, c, …, z and the blank.

출력

The output must contain a single line with an integer representing the maximal level of complexity $Lc(T)$.

제한

  • $2 \le n \le 1000000$
  • The length of any of the toponyms will not exceed 20000 characters.
  • The size of the input file will not exceed 10 Megabytes.

예제 입력 1

7
Jora de Sus
Orhei
Jora de Mijloc
Joreni
Jora de Jos
Japca
Orheiul Vechi

예제 출력 1

24