시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 1024 MB 4 3 3 100.000%

문제

Your friend likes money. When your friend has a name day he or she gets money from their nice aunt, hence your friend really enjoys when they have a name day.

It happens to be your friend's name day today, and your friend is considering how they could avoid having to wait another whole year before it's time for name day again. You've been asked to help out.

Your friend is planning to replace exactly one letter in their name in order to have a name day as soon as possible again. Given a list of name days for the coming year, please help your friend decide how soon they can have a name day again. It's forbidden to add or erase characters, you may only replace exactly one character with exactly one other character.

If it's impossible to find a name that can be reached with the above listed allowed actions, your friend will simply have to wait a whole year.

입력

Input starts with a single string, the name of your friend. Then follows an integer $N$ on one row, the number of days in the coming year. After that follows $N$ strings, the name days for days in the coming year.

The $N$:th name will always be the name of your friend, since it's their name day today and hence also in exactly one year again. The names in the input consist solely of characters a-z, contain no spaces and are at most 10 characters long. All names for the coming year will be different.

출력

Output a single integer on a single line: the minimum number of days before it's time for name day again, if you help your friend cheat with their name.

서브태스크

번호 배점 제한
1 53

$1 \le N \le 50$

2 47

$1 \le N \le 10\,000$

예제 입력 1

anna
5
peter
petra
anja
markus
anna

예제 출력 1

3

예제 입력 2

jan
3
petra
bengt
jan

예제 출력 2

3

예제 입력 3

anya
4
ana
hanya
enya
anya

예제 출력 3

3

힌트

In the first sample input your friend's name is anna. She can make the name anja by replacing the second n in her name with a j, and thus she has a name day two days earlier than expected. Thus the answer is 3. In the second sample input it's impossible to create another name using the above listed actions, so jan will have to wait a whole year, 3 days.

출처

Olympiad > Swedish Olympiad in Informatics > 2016 > Online Qualification A번

  • 문제를 만든 사람: Oskar Werkelin Ahlin

채점 및 기타 정보

  • 예제는 채점하지 않는다.