← 返回题目列表

AtCoder · awc0110_e

E. 缩写分配

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

分数: 433 分

问题陈述

Takahashi 正在开发供其公司内部使用的联系人列表系统。每个员工都有一个唯一的用户名,但由于用户名很长,他决定实现一个功能,分配一个 缩写 给每位员工。

有 N 员工,以及该员工的用户名 i-第员工是一个字符串 S_i 由小写英文字母组成。对于每位员工 i,正好一个 非空前缀 他们的用户名 选择并指定 S_i 作为其缩写 T_i。也就是说, T_i 必须是由第一个组成的字符串 1 to |S_i| 的字符 S_i。也允许使用整个用户名作为缩写。

缩写赋值 (T_1, T_2, \ldots, T_N) 必须满足以下条件 无前缀条件:

  • 无前缀条件:对于任意两个不同的员工 i, j (i \neq j), T_i 不是以下的前缀 T_j,和 T_j 不是以下的前缀 T_i.

这里是一个字符串 A 是字符串的前缀 B if |A| \leq |B| 和第一个 |A| 的字符 B 匹配 A。特别是,当 A = B, A 也是前缀 B.

因此,根据无前缀条件,有 T_i = T_j 对于不同的员工 i, j (i \neq j)也是不允许的。

高桥希望最大限度地减少 缩写总长度 \sum_{i=1}^{N} |T_i| 如果存在有效的缩写分配。如果存在有效分配,则输出最小总长度;否则,输出 -1.

约束

  • 1 \leq N \leq 2 \times 10^5
  • S_i 是由小写英文字母组成的字符串。
  • 1 \leq |S_i| \leq 5 \times 10^5
  • If i \neq j,那么 S_i \neq S_j (所有用户名都是不同的)。
  • \sum_{i=1}^{N} |S_i| \leq 5 \times 10^5

输入

N
S_1
S_2
\vdots
S_N

第一行包含一个整数 N 代表员工人数。的 i- 以下各项 N 行包含一个字符串 S_i 代表用户名 i第员工。

输出

如果存在有效的缩写分配,则在单行上输出缩写的最小总长度。如果不存在有效分配,则输出 -1.


示例输入 1

3
alice
bob
carol

示例输出 1

3

示例输入 2

2
a
ab

示例输出 2

-1

示例输入 3

12
apple
apricot
banana
bandit
banner
candle
canary
cattle
dog
dove
duck
zebra

示例输出 3

38

示例输入 4

40
aaaaaa
aaaaab
aaaaac
aaaaad
aaaaae
aaaaba
aaaabb
aaaabc
aaaabd
aaaabe
aaabaa
aaabab
aaabac
aaabad
aaabae
aaabba
aaabbb
aaabbc
aaabbd
aaabbe
aabaaa
aabaab
aabaac
aabaad
aabaae
aababa
aababb
aababc
aababd
aababe
abaaaa
abaaab
abaaac
abaaad
abaaaae
ababaa
ababab
ababac
ababad
ababae

示例输出 4

-1

示例输入 5

1
a

示例输出 5

1