Problem K
Hraðskrif
Languages
en
is
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 |
