Identity Theft

시간 제한3초메모리 제한1024 MB

요약

N개의 이진 문자열이 주어질 때, 각 문자열 뒤에 비트를 덧붙여 어떤 문자열도 다른 문자열의 접두사가 되지 않도록 하면서 추가한 비트 수의 합을 최소화한다.

난이도: 어려움10점 중 8점
유형: 트라이, 그리디, 트리, DFS
정답자: 아직 제출이 없습니다

문제

Farmer John's $N$ ( $1 \leq N \leq 10^5$ ) cows each have a Farm ID number in the form of a bitstring (a string consisting of the characters '0' and '1'). Bessie, the eldest cow, has the Farm ID numbers of all the cows memorized, and likes to go around and ask cows their ID numbers.

When a cow is asked their Farm ID number, they will start to say the correct bitstring, but may get confused and stop before finishing it. When Bessie hears the bitstring, if it is not the Farm ID number of any cow on the farm, then she will shrug and walk off. However, if it is the ID number of a different cow than the one she asked, then she will assume that identity theft has occurred and place the farm into lockdown. Note that this can happen even when the cow says their full Farm ID number.

Farmer John would like to prevent this from happening, and is willing to change the cows' Farm ID numbers by adding some more bits to them. In one second, he can add one bit to the end of the Farm ID number of any cow. Figure out the minimum amount of time it will take for him to prevent a lockdown from ever occurring.

입력

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

Then $N$ lines follow. The $k$ th line contains a bitstring equal to the Farm ID number of the $k$ th cow on Farmer John's farm.

No cow's Farm ID number is empty, and the total length of all Farm ID numbers is at most $10^6$ .

출력

Output the minimum number of seconds Farmer John needs to spend to ensure that a lockdown will never occur.

예제5

예제 1
입력
```
3
1
1
1
```
예상 출력
```
5
```
예제 2
입력
```
3
1
11
111
```
예상 출력
```
2
```
예제 3
입력
```
3
1
1
11
```
예상 출력
```
4
```
예제 4
입력
```
5
0
01
0011
010
01
```
예상 출력
```
6
```
예제 5
입력
```
14
0
1
1
0
1
0
1
1
1
1
1
0
0
1
```
예상 출력
```
41
```