시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB52221742.500%

문제

Bajtazar is a member of the jury for the Find Your Palace Contest, a prestigious programming competition that offers a luxurious palace to the winner. He is now trying to come up with a name for his problem. According to Bajtazar, a good problem name consists of exactly two words. Additionally, Bajtazar finds alliterations very annoying, so he will remove the first letter from both words until the first letter of the two words is different or one of them becomes empty. After this operation, Bajtazar defines the goodness of the problem name as the sum of lengths of the two words.

He has prepared a list of $n$ words, and started to wonder what is the maximum goodness that can be achieved using the words from the list. Bajtazar himself does not have time to answer that question as he is busy reinforcing the tests with nasty edge cases. Help Bajtazar by finding the maximum goodness that can be achieved.

입력

The input consists of:

  • One line with an integer $n$ ($2\leq n\leq 2\cdot10^5$), the number of words.
  • $n$ lines, each with a word $w$ ($1\leq |w|\leq 10^6$). Each word only consists of English lowercase letters (a-z).

The total number of characters in the $n$ words is at most $10^6$.

출력

Output the maximum goodness that can be achieved.

예제 입력 1

3
amsterdam
is
amazing

예제 출력 1

12

예제 입력 2

3
bbb
abbba
aaba

예제 출력 2

8

예제 입력 3

2
abcdefghijklmnopqrstuvwxyz
abcdefghijklmnopqrstuvwxyz

예제 출력 3

0

출처

University > Delft University of Technology > Freshmen Programming Contest 2024 A번

  • 문제를 만든 사람: Maciek Sidor