Toponyms

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; or Jora de Sus, Jora de Mijloc and Jora de Jos.

As a rule, every toponym is a sequence consisting of the characters A, B, C, …, Z, a, b, c, …, z and the blank character. In a toponym there cannot appear two or more consecutive blanks. Toponyms have no leading or trailing blanks. The subsequence consisting of the first $m$ characters of a 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.

• The level of similarity $Ls(T)$ of a set $T$ of toponyms is defined as the length of the longest common prefix of the toponyms in $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$.
• The 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$, finds the subset $T$ ($T \subseteq S$) with the maximal level of complexity, and outputs that maximal value.

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

Output a single line containing an integer, the maximal level of complexity $Lc(T)$.

• $2 \le n \le 1000000$
• The length of any toponym does not exceed 20000 characters.
• The size of the input does not exceed 10 megabytes.