← 返回题目列表

Codeforces · 965/E

E. 短代码

中文机器翻译题面 查看原题

Arkady 的代码包含 $$$n$$$ 变量。每个变量都有一个唯一的名称,仅由小写英文字母组成。有一天,阿尔卡迪决定缩短他的代码。

他希望将每个变量名称替换为其非空前缀,以便这些新名称仍然是唯一的(但是,某些变量的新名称可以与另一个或同一变量的某些旧名称重合)。在这些可能性中,他想找到新名称总长度尽可能最小的方法。

如果您可以从 $$$b$$$ 末尾删除一些(可能没有)字符并获得 $$$a$$$,则字符串 $$$a$$$ 是字符串 $$$b$$$ 的前缀。

请找出新名称的最小可能总长度。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 变量的数量。

接下来的 $$$n$$$ 行包含变量名称,每行一个。每个名称都非空且仅包含小写英文字母。这些字符串的总长度不大于$$$10^5$$$。变量名称是不同的。

输出

打印单个整数——新变量名称的最小可能总长度。

示例

输入 #1

3
codeforces
codehorses
code

输出 #1

6

输入 #2

5
abba
abb
ab
aa
aacada

输出 #2

11

输入 #3

3
telegram
digital
resistance

输出 #3

3

注意

在第一个示例中,最佳选项之一是将给定顺序的名称缩短为“cod”、“co”、“c”。

在第二个示例中,我们可以将姓氏缩短为“aac”,将名字缩短为“a”,而不更改其他名称。