Fixing Shirts

View as PDF

Points: 15
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type

Troy is preparing for this year's CCO, which has participants. Each participant has a shirt size, either large or small, and a preferred colour. He has ordered shirts for the participants, where (he ordered some spares).

Unfortunately, Troy noticed that the shirts came in wrong! Although he received shirts, they are not the shirts he needs. He might not be able to give everyone their preferred colour and required size.

Thankfully, Troy has a Very-Handy-Gadget. In one second, Troy can use his Very-Handy-Gadget to change either the size or the colour of any shirt.

Troy needs to distribute the shirts soon! How many seconds does he need so all participants get their required size and preferred colour?

Input Specification

The first line contains two integers: and .

Then lines follow. The line contains the required size of the participant, either L or S, and the preferred colour , an integer.

Then lines follow. The line contains the size of the shirt, either L or S, and the colour , an integer.

Output Specification

Output a single integer, the minimum number of seconds Troy needs to give every participant the correct shirt, or if Troy does not need to change any shirts.

Sample Input 1

1 3
L 1
S 3
S 2
S 1

Output for Sample Input 1

1

Explanation for Sample Output 1

Troy should change the size of the shirt to large, taking a total of one second.

Sample Input 2

3 4
L 1
S 2
L 3
S 3
S 2
S 4
L 2

Output for Sample Input 2

2