Код Эвана содержит n переменных. Каждая переменная имеет уникальное имя, состоящее только из английских строчных (маленьких) букв. Однажды Эван решил укоротить свой код.
Он хочет заменить имя каждой переменной его непустым префиксом таким образом, что новые имена останутся попарно различными (но новое имя какой-либо переменной может совпадать со старым именем этой или другой переменной). Среди всех таких возможных замен он хочет найти такую, для которой суммарная длина названий переменных будет минимальной.
Строка a является префиксом строки b, если вы можете удалить несколько (возможно, ни одного) символа с конца строки b и получить a.
Найдите минимальную возможную суммарную длину новых имён.
Входные данные:
В первой строке содержится одно целое число n (1 ≤ n ≤ 10
5) — число переменных в коде Эвана.
Следующие n строк содержат названия переменных по одному на строку. Каждое название не является пустой строкой и содержит только лишь строчные (маленькие) английские буквы. Суммарная длина всех этих строк не больше 10
5. Все названия переменных различны.
Выходные данные:
Выведите одно целое число — минимально возможную суммарную длину новых названий переменных.
Примеры:
| Входные данные |
Выходные данные |
3
codeforces
codehorses
code |
6 |
5
abba
abb
ab
aa
aacada |
11 |
3
telegram
digital
resistance |
3 |
Пояснения:
В первом примере одним из наилучших вариантов будет сокращение имён в порядке их ввода до "cod", "co", "c".
Во втором примере можно укоротить последнее имя до "aac" и первое имя до "a" без изменения других имён переменных.