Problem
El código de Evan contiene n variables. Cada variable tiene un nombre único, que consta solo de letras minúsculas (pequeñas) en inglés. Un día, Evan decidió acortar su código.
Quiere reemplazar el nombre de cada variable con su prefijo no vacío de tal manera que los nuevos nombres permanezcan separados por pares (pero el nuevo nombre de alguna variable puede ser el mismo que el antiguo nombre de esta u otra variable). Entre todos esos reemplazos posibles, quiere encontrar uno para el cual la longitud total de los nombres de las variables sea mínima.
La cadena a es un prefijo de la cadena b si puede eliminar algunos caracteres (posiblemente ninguno) del final de la cadena b y obtener a.
Encuentre la longitud total mínima posible de nuevos nombres.
Entrada:
La primera línea contiene un único número entero n (1 ≤ n ≤ 10
5) — número de variables en el código de Evan.
Las siguientes n líneas contienen nombres de variables, uno por línea. Cada nombre no es una cadena vacía y contiene solo letras minúsculas (pequeñas) en inglés. La longitud total de todas estas cadenas no supera los 10
5. Todos los nombres de variables son diferentes.
Salida:
Imprime un solo entero — la longitud total mínima posible de nuevos nombres de variables.
Ejemplos:
| Entrada |
Salida |
3
código |
6 |
5
abba
ab
ab
aa
aacada |
11 |
3
telegrama
digitales
resistencia |
3 |
Explicaciones:
En el primer ejemplo, una de las mejores opciones sería acortar los nombres en el orden en que se ingresan a "cod", "co", "c".
En el segundo ejemplo, puede acortar el apellido a "aac" y nombre antes de "a" sin cambiar otros nombres de variables.