Hide

Problem C
Hraðskrif

Languages en is
/problems/hradskrif/file/statement/en/img-0001.jpg
Keyboard by DomAlberts, Pixabay
Fast typing is a handy skill in competitive programming. Bjarki practices a lot on TypeRacer to maximize the number of words he can type per minute. Sometimes Bjarki would like to press the TAB key on his keyboard and instantly type the word he is thinking. This would save him a lot of time, but is only possible if there is only one possible word.

Bjarki has prepared a dictionary on his computer that contains all the words that may appear. For example, it takes $26$ key presses to type ANNA OG AMMA ETA MAT SAMAN. If he uses the dictionary and types AN! O! AM! E! M! S!, where ! denotes that Bjarki presses the TAB key, then he presses $19$ keys, saving $7$. Note that he can’t press the TAB key immediately after typing A because it is not clear whether he is typing ANNA or AMMA. Note also that if there is only one word in the dictionary then Bjarki can press the TAB key straight away, without typing a single letter in the word.

Given the text that Bjarki wants to write determine the maximum number of key presses saved.

Input

The first line of the input contains a single integer $1 \leq n \leq 5 \cdot 10^5$, the number of words Bjarki wants to type. The next line contains the text Bjarki wants to type. The text consists of one or more words, separated by spaces, and the total number of characters is less than $10^6$. The words contain only letters in the English alphabet.

Output

Print the maximum number of key presses Bjarki can save.

Scoring

Group

Points

Constraints

1

30

$1 \leq n \leq 10$ and each word is at most $10$ characters long

2

40

Each word is at most $10$ characters long

3

30

No further constraints

Sample Input 1 Sample Output 1
6
ANNA OG AMMA ETA MAT SAMAN
7
Sample Input 2 Sample Output 2
7
BARBARA ARA BAR ARA ARABA BARA RABBABARA
9
Sample Input 3 Sample Output 3
1
INSTANT
6

Please log in to submit a solution to this problem

Log in