Problem Background

Note: The time limit and memory limit for this problem are 3 seconds and 512MB, respectively, which are 1.5 times and 2 times the usual limits.

Problem Description

Farmer John has $N$ ($1 \le N \le 10^5$) cows, each with a farm ID in the form of a binary string (a string consisting of characters 0 and 1). Bessie, the eldest cow, remembers the farm IDs of all cows and enjoys asking cows about their farm IDs.

When a cow is asked about her farm ID, she starts reporting the correct binary string but may become confused and stop before finishing. When Bessie hears this binary string, if it does not match the farm ID of any cow on the farm, she shrugs and walks away. However, if it matches the farm ID of another cow different from the one she asked, she believes identity theft has occurred and will lock down the entire farm. Note that this can happen even when the cow reports her full farm ID.

Farmer John wants to prevent this situation and is willing to change the cows' farm IDs by adding more binary digits. He can add one binary digit to the end of any cow's farm ID in one second. Determine the minimum time he needs to prevent a lockdown.

Input Format

The first line of input contains $N$, the number of cows on Farmer John's farm.

The next $N$ lines, the $k$-th line contains the binary string representing the farm ID of the $k$-th cow on Farmer John's farm.

All farm IDs are non-empty, and the total length of all farm IDs does not exceed $10^6$.

Output Format

Output the minimum number of seconds Farmer John needs to ensure a lockdown does not occur.

Sample Input and Output

Sample Input #1

3
1
1
1

Sample Output #1

5

Sample Input #2

3
1
11
111

Sample Output #2

2

Sample Input #3

3
1
1
11

Sample Output #3

4

Sample Input #4

5
0
01
0011
010
01

Sample Output #4

6

Sample Input #5

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

Sample Output #5

41

Notes/Hints

Sample Explanation 1

This example satisfies the properties of the first subtask.

We can spend 5 seconds to make a lockdown impossible by adding 0 to the first farm ID, 10 to the second farm ID, and 11 to the third farm ID, making the farm IDs 10, 110, and 111. You can prove this cannot be done in 4 seconds or less. For example, if you keep all farm IDs unchanged, all 3 cows have the same farm ID 1, so when Bessie hears it, it will always match another cow's farm ID.

As another example, if you spend only 2 seconds by adding 0 to the second farm ID and 1 to the third farm ID, the farm IDs become 1, 10, and 11, so the second and third cows, when reporting their farm IDs, might stop in the middle and report only 1, which will match the first cow's farm ID.

Sample Explanation 2

We can make a lockdown impossible in 2 seconds by adding 0 to the first two farm IDs, making the farm IDs 10, 110, and 111 as before. You can prove this cannot be done in 1 second.

Sample Explanation 3

We can make a lockdown impossible in 4 seconds by adding 00 to the first farm ID and 01 to the second farm ID. You can prove this cannot be done in 3 seconds or less.

Sample Explanation 5

This example satisfies the properties of the first subtask.

Test Case Properties

• Test cases $6-7$: All farm IDs have a length of exactly 1.
• Test cases $8-15$: $N \le 10^2$, and the total length of all farm IDs does not exceed $10^3$.
• Test cases $16-25$: No additional restrictions.

见题面 Input 部分

见题面 Output 部分