Annoying Alliterations

Interview

Time limit2sMemory limit1024 MB

Summary

Given n words, find the two words whose combined length is maximized after stripping leading letters from both while their first letters match.

Level: Medium6 of 10
Topics: Trie, String, Greedy
Solved: No attempts yet

Statement

Bajtazar is a member of the jury for the Find Your Palace Contest, which gives a luxurious palace to the winner. He is now naming his problem. A good problem name consists of exactly two words. Bajtazar finds alliterations annoying, so he removes the first letter from both words until the first letters of the two words differ or one of the words becomes empty. After this operation, the goodness of the name is the sum of the lengths of the two words.

He has a list of $n$ words. Find the maximum goodness that can be achieved using words from the list. Bajtazar is busy adding nasty edge cases to the tests, so help him find it.

Input

The first line contains an integer $n$ ( $2 \leq n \leq 2 \cdot 10^5$ ), the number of words. Each of the next $n$ lines contains a word $w$ ( $1 \leq |w| \leq 10^6$ ). Each word consists only of lowercase English letters (a-z). The total number of characters in the $n$ words is at most $10^6$ .

Output

Output the maximum goodness that can be achieved.

Examples3

Example 1
Input
```
3
amsterdam
is
amazing
```
Expected output
```
12
```
Example 2
Input
```
3
bbb
abbba
aaba
```
Expected output
```
8
```

Example 3

Input

2
abcdefghijklmnopqrstuvwxyz
abcdefghijklmnopqrstuvwxyz

Expected output