[ARC175] F - Append Same Characters

F - Append Same Characters

Time Limit: 4 sec / Memory Limit: 1024 MB

题面

分数: 1000 分

给定 个由小写英文字母组成的字符串 。考虑按照以下两种操作任意次序零次或多次地执行：

• 选择一个小写字母 。将 追加到 的末尾，其中 。
• 选择一个整数 ，满足 。交换 和 。

求使得对所有 ，（词典序）成立所需的最小总操作次数。

什么是词典序呢？

一个字符串 被称为 词典序更小，如果满足以下条件1或2。这里， 和 分别表示 和 的长度。

1. 且 。
2. 存在一个整数 ，使得以下两个条件同时成立：
   • 。
   • 字母 在字母表顺序中位于 之前。

限制条件

• 所有输入值均为整数。
• 是由小写英文字母组成的字符串。

---

输入

输入采用标准输入格式，具体如下：

输出

在一行中输出答案。

---

输入样例 1

5
ab
rac
a
dab
ra

输出样例 1

3

以下是一种操作方式。

• 交换 和 。现在 ab, a, rac, dab, ra。
• 对每个字符串追加 z 到末尾。现在 abz, az, racz, dabz, raz。
• 交换 和 。现在 abz, az, dabz, racz, raz。此时，我们有 对所有 成立。

无法在少于三次操作的情况下使得对所有 ， 成立，因此应该输出 。

---

输入样例 2

3
kitekuma
nok
zkou

输出样例 2

0

在执行任何操作之前，我们有对所有 ， 成立。

---

输入样例 3

31
arc
arrc
rc
rac
a
rc
aara
ra
caac
cr
carr
rrra
ac
r
ccr
a
c
aa
acc
rar
r
c
r
a
r
rc
a
r
rc
cr
c

输出样例 3

175

请注意，对于 可能存在 。