题目背景

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

题目描述

Farmer John 的 $N$（$1\le N\le 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

3
1
11
111

2

3
1
1
11

4

5
0
01
0011
010
01

6

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

41

提示

样例解释 1

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

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

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

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

样例解释 2

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

样例解释 3

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

样例解释 5

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

测试点性质

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