URI Online Judge | 2947

Correct Answers

By Francisco Elio Parente Arcos Filho, Universidade do Estado do Amazonas BR Brazil

Timelimit: 1

Desafortunato is a high school student in a prestigious school. The tests in this school are famous for having a well defined format but also for being of a very high level. They are always objective, that is, they are composed of a statement and several options of answer listed with capital letters, but, unlike the traditional objective tests, each question of the test in that college has 26 options of answer, using all the letters of the English alphabet. And only one of these options is correct.

This year, the Desafortunato class intends to win the best class of the college award, which grants some privileges to extra-class activities. And to achieve this goal the class must have the highest sum of grades in the final exam. What worried enough Desafortunato that after having done the final test he fears not to have performed well.

Concerned also with the prize at stake and knowing that Desafortunato is well known for his bad luck, the class wants to estimate what their chances of winning considering the worst of cases about their unlucky colleague: He failing in all the answers.

Given the copy of the answer sheets of all the students in the class and considering that Desafortunato get wrong all questions of the test, calculate what the largest sum of grades that the class can still achieve.

Remember that in a answer sheet the first letter corresponds to the student's answer to the first question of proof, the second letter corresponds to the answer of the second question and so on.

Input

The first line of input consists of an integer K (1 ≤ K ≤ 102) representing the number of questions in the test. The second line of the input consists K uppercase letters of the English alphabet without blanks representing the Desafortunato's answers. The third line contains an integer N (1 ≤ N ≤ 102) representing the number of Desafortunato's classmates. The next N lines contains K uppercase letter of english alphabet each without white space. Each line corresponds to the answer sheet of a Desafortunato's colleague.

Output

The output consists of a single line containing the largest sum of notes that the class can get.

Input Samples Output Samples

3

ABC

3

ACB

CBA

BAC

3

5

BCDEA

3

ABCDE

BBDDE

BEDDK

9

6

FEDBAC

5

PMKJAA

QNKBFD

FOKBFD

QMKBFD

RNKJBA

17