Problem
O código de Evan contém n variáveis. Cada variável tem um nome exclusivo, consistindo apenas em letras minúsculas (pequenas) do inglês. Um dia Evan decidiu encurtar seu código.
Ele deseja substituir o nome de cada variável por seu prefixo não vazio de forma que os novos nomes permaneçam distintos aos pares (mas o novo nome de alguma variável pode ser o mesmo que o antigo nome desta ou de outra variável). Entre todas as substituições possíveis, ele deseja encontrar uma para a qual o comprimento total dos nomes das variáveis seja mínimo.
A string a é um prefixo da string b se você puder remover alguns (possivelmente nenhum) caracteres do final da string b e obter a.
Encontre o comprimento total mínimo possível de novos nomes.
Entrada:
A primeira linha contém um único inteiro n (1 ≤ n ≤ 10
5) — número de variáveis no código de Evan.
As próximas n linhas contêm nomes de variáveis, um por linha. Cada nome não é uma string vazia e contém apenas letras minúsculas (pequenas) em inglês. O comprimento total de todas essas strings não passa de 10
5. Todos os nomes de variáveis são diferentes.
Saída:
Imprima um único inteiro — o comprimento total mínimo possível de novos nomes de variáveis.
Exemplos:
| Entrada |
Saída |
3
código |
6 |
5
aba
abb
ab
aa
aacada |
11 |
3
telegrama
digitais
resistência |
3 |
Explicações:
No primeiro exemplo, uma das melhores opções seria encurtar os nomes na ordem em que são inseridos para "cod", "co", "c".
No segundo exemplo, você pode encurtar o sobrenome para "aac" e primeiro nome antes de "a" sem alterar outros nomes de variáveis.