Problem
Le code d'Evan contient n variables. Chaque variable a un nom unique, composé uniquement de lettres minuscules en anglais. Un jour, Evan a décidé de raccourcir son code.
Il souhaite remplacer le nom de chaque variable par son préfixe non vide de manière à ce que les nouveaux noms restent deux à deux distincts (mais le nouveau nom d'une variable peut être le même que l'ancien nom de cette variable ou d'une autre). Parmi tous ces remplacements possibles, il souhaite en trouver un pour lequel la longueur totale des noms de variables sera minimale.
La chaîne a est un préfixe de la chaîne b si vous pouvez supprimer certains caractères (éventuellement aucun) de la fin de la chaîne b et obtenir a.
Trouvez la longueur totale minimale possible des nouveaux noms.
Saisie :
La première ligne contient un seul entier n (1 ≤ n ≤ 10
5) — nombre de variables dans le code d'Evan.
Les n lignes suivantes contiennent des noms de variables, un par ligne. Chaque nom n'est pas une chaîne vide et ne contient que des lettres anglaises minuscules (petites). La longueur totale de toutes ces chaînes ne dépasse pas 10
5. Tous les noms de variables sont différents.
Sortie :
Imprimer un seul entier — la longueur totale minimale possible des nouveaux noms de variables.
Exemples :
| Entrée |
Sortie |
3
code |
6 |
5
Abba
ab
ab
aa
aacada |
11 |
3
télégramme
numérique
résistance |
3 |
Explications :
Dans le premier exemple, l'une des meilleures options serait de raccourcir les noms dans l'ordre dans lequel ils sont entrés en "cod", "co", "c".
Dans le deuxième exemple, vous pouvez raccourcir le nom de famille en "aac" et prénom avant "a" sans changer les autres noms de variables.