Namnsdag
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
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
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.
Explanation of sample
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.
Scoring
Your solution will be tested on a number of test case groups. To get points for a group you have to solve all the test cases in that group.
|
Group |
Points |
Limits |
Other |
|
1 |
53 |
$1 \le N \le 50$ |
|
|
2 |
47 |
$1 \le N \le 10\, 000$ |
| Sample Input 1 | Sample Output 1 |
|---|---|
anna 5 peter petra anja markus anna |
3 |
| Sample Input 2 | Sample Output 2 |
|---|---|
jan 3 petra bengt jan |
3 |
| Sample Input 3 | Sample Output 3 |
|---|---|
anya 4 ana hanya enya anya |
3 |
