Problem N
Password Predictor

Source: PixaBay

You’re trying to log into your computer, but you can’t quite remember your password! The only pieces of information that you can remember is that your password contains only capital letters in addition to the “?” and “!” characters. Your computer also requires your password to be of a specific length, which you remember. Thankfully, you turned on password hinting before you locked your computer. In the version of password hinting that you use, the system will tell you the “similarity” of any password that you try with the true password. This similarity is calculated by counting the number of characters in the attempted password that are correctly placed. You only have a certain number of guesses and you don’t want to get locked out so you make a list of all passwords that you think might be correct.

Input

The input consists of a single test case. The first line contains a single integer $l$ ($1 \le l \le 1\, 000$), the length of the password that your system requires to successfully log you in. The next line contains a single integer $t$ ($1 \le t \le 1\, 000$), the number of passwords that you’ve already tried. The next $t$ lines contain two space-separated items: a $l$-character password that you’ve already guessed and a single integer $s$ ($0 \le s \le l$), the similarity of that password with the actual password. All of the passwords that you have already guessed will be unique. The next line contains a single integer $g$ ($1 \le g \le 1\, 000$), the number of possible passwords that you have on your list. The next $g$ lines each contain a unique $l$-character password that you suspect might be your true password.

Output

Output a single integer, the number of passwords from your list that could possibly be your true password, based on the information from your tries.

9
2
GOHOKIES! 0
ISTHISIT? 3
6
IDONTKNOW
PYTHONFTW
MYPASSWRD
!STRUCT??
THISISIT!
ISLANDS!?

3