신원 도용

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

난이도: 아직 분류되지 않았습니다
정답자: 아직 제출이 없습니다

문제

Farmer John의 소 $N$ 마리( $1 \leq N \leq 10^5$ )에게는 각각 농장 ID 번호가 있다. 농장 ID 번호는 '0'과 '1' 문자만으로 이루어진 비트열이다. 가장 나이 많은 소인 Bessie는 모든 소의 농장 ID 번호를 외우고 있고, 돌아다니면서 소들에게 ID 번호를 묻는 것을 좋아한다.

농장 ID 번호를 질문받은 소는 올바른 비트열을 말하기 시작하지만, 혼란스러워서 끝까지 말하기 전에 멈출 수도 있다. Bessie는 그 비트열을 들었을 때 농장의 어떤 소의 ID 번호도 아니면 어깨를 으쓱하고 떠난다. 하지만 질문한 소가 아닌 다른 소의 ID 번호라면 신원 도용이 일어났다고 판단하고 농장을 봉쇄한다. 소가 전체 농장 ID 번호를 다 말한 경우에도 이런 일이 생길 수 있다.

Farmer John은 이런 일을 막고 싶어 한다. 1초 동안 임의의 소의 농장 ID 번호 끝에 비트 하나를 덧붙일 수 있다. 봉쇄가 절대 일어나지 않도록 하는 데 필요한 최소 시간을 구하라.

입력

첫 줄에 Farmer John의 농장에 있는 소의 수 $N$ 이 주어진다.

이어서 $N$ 개의 줄이 주어지며, 각 줄에는 해당 소의 농장 ID 번호인 비트열이 주어진다.

농장 ID 번호는 모두 비어 있지 않으며, 모든 농장 ID 번호 길이의 합은 $10^6$ 이하이다.

출력

봉쇄가 절대 일어나지 않도록 하는 데 Farmer John이 써야 하는 최소 초를 출력한다.

예제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
```