Problem 1. Identity Theft

USACO 2024 US Open Contest, Platinum

注意：本题的时间限制和内存限制为 3 秒 和 512MB，分别为通常限制的 1.5 倍和 2 倍。

Farmer John 的 $N$（$1 \leq N \leq 10^5$）头奶牛每头都有一个二进制字符串（由字符 '0' 和 '1' 组成的字符串）形式的农场证号。Bessie，最年长的奶牛，记住了所有奶牛的农场证号，还喜欢到处询问奶牛她们的农场证号。

当一头奶牛被询问她的农场证号时，她们会开始报正确的二进制字符串，但有可能会感到困惑并在报完之前停下来。当 Bessie 听到该二进制字符串时，如果它不等于农场上任何一头奶牛的农场证号，她就会耸耸肩走开。然而，如果它等于不同于她所询问的奶牛的另一头奶牛的农场证号，那么她就会认为发生了身份盗用并封锁整个农场。注意，这种情况即使当奶牛报出完整的农场证号时也可能发生。

Farmer John 希望防止这种情况发生，并愿意以添加更多二进制位的方式改变奶牛的农场证号。他可以在一秒钟内在任意一头牛的农场证号末尾添加一个二进制位。求出他所需要的最小时间以防止封锁发生。

输入格式（从终端 / 标准输入读入）：

输入的第一行包含 $N$，为 Farmer John 的农场上的奶牛数量。

以下 $N$ 行，第 $k$ 行包含表示 Farmer John 的农场上第 $k$ 头奶牛的农场证号的二进制字符串。

所有奶牛的农场证号均不为空，且所有农场证号的总长度不超过 $10^6$。

输出格式（输出至终端 / 标准输出）：

输出 Farmer John 需要花费的最小秒数以确保封锁不会发生。

输入样例：

3
1
1
1

输出样例：

5

这一样例满足第一个子任务的性质。

我们可以花费 5 秒使得封锁不可能发生，通过对第一个农场证号添加 "0"，对第二个农场证号添加 "10"，对第三个农场证号添加 "11"，使农场证号变为 "10"，"110" 和 "111"。

你可以证明这不可能在 4 秒或更少的时间内完成。例如，如果你保持所有农场证号不变，则所有 3 头奶牛都具有相同的农场证号 "1"，因此当 Bessie 听到它时，它将始终等于另一头奶牛的农场证号。

作为另一个例子，如果你仅花费 2 秒对第二个农场证号添加 "0"，对第三个农场证号添加 "1"，则农场证号变为 "1"，"10" 和 "11"，因此第二头和第三头奶牛在报她们的农场证号时，可能会停在中间只报出 "1"，而这将等于第一头奶牛的农场证号。

输入样例：

3
1
11
111

输出样例：

2

我们可以在 2 秒内使得封锁不可能发生，通过对前两个农场证号添加 "0"，像之前一样使农场证号变为 "10"，"110" 和 "111"。你可以证明这不可能在 1 秒内完成。

输入样例：

3
1
1
11

输出样例：

4

我们可以在 4 秒内使得封锁不可能发生，通过对第一个农场证号添加 "00"，对第二个农场证号添加 "01"。你可以证明这不可能在 3 秒或更少的时间内完成。

输入样例：

5
0
01
0011
010
01

输出样例：

6

输入样例：

14
0
1
1
0
1
0
1
1
1
1
1
0
0
1

输出样例：

41

这一样例满足第一个子任务的性质。

测试点性质： 测试点 6-7：所有农场证号的长度均恰好为 $1$。测试点 8-15：$N\le 10^2$，且所有农场证号的总长度不超过 $10^3$。测试点 16-25：没有额外限制。

供题：Benjamin Qi