URI Online Judge | 2117

Help Me Master

By Rogério Júnior, Noic BR Brazil

Timelimit: 2

Master Null Yard is coordinator of Farias Brito who uses his large network on FB (FariasBook) to help young students who want to study at the organization. Recently, he decided to increase even more his number of friends, and he will do it commenting on random photos of friends' friends.

Based on a recent study of the reputed research institute FBideias, Master knows that certain person i will accept his friend request after he commented a string S on one of his photos if the person’s favorite letter apeears at least Ki times in S. It doesn’t matter if the letter is uppercase or lowercase.

As he is carrying the name of the Organization, Master sent all his possible comments to FBideias, and received a list of the N comments which were approved as pollitically correct, but since FariasBook has a very rigid policy agains SPAM, he can’t comment the same string on two distinct photos.

Jogério Rúnior studies for olympiads in informatics, so Master decided to ask him for help in two problems: fixing his printer and choosing what to comment on each photo in such a way that his number of friends increases the greatest possible amount. Jogério noticed the the printer had only a loose cable, solved this issue and gave to you, the new student Fia Breire, the mission to comment on the photos. Help the Master!

Input

The first line of the input contains two integers: N and M (3 ≤ N, M ≤ 1000), the number of strings on the list that Master received and the number of people who are his friends' friends, respectively. The next N lines will contain each one of the strings on the list that he received. Each line represents a comment. Due to FariasBook restrictions, each comment contains no more than 140 characters, which must be letters (uppercase or lowerase) or spaces. The next M lines will contain, each one, a uppercase letter ci and and integer Ki, which represent, respectively, person’s i favorite letter and how many times it must appear in order to that person accept Master’s friend request.

Output

Your program must output a single line with and only integer: the greatest number of friends Master might get.

Input Sample Output Sample

4 3

BOM dIa MesTRE

MESTRE ME AJUDE caMIsa DEz

TimE Fb

Patio ZERO

E 4

Z 1

M 3

2