Fixing Shirts

View as PDF

Submit solution

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

Problem type

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

Unfortunately, Troy noticed that the shirts came in wrong! Although he received M 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?


1 \le N \le M \le 1\,000\,000

1 \le c_i \le 10^9

1 \le k_j \le 10^9

Input Specification

The first line contains two integers: N and M.

Then N lines follow. The i^\text{th} line contains the required size of the i^\text{th} participant, either L or S, and the preferred colour c_i, an integer.

Then M lines follow. The j^\text{th} line contains the size of the j^\text{th} shirt, either L or S, and the colour k_j, an integer.

Output Specification

Output a single integer, the minimum number of seconds Troy needs to give every participant the correct shirt, or 0 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


Explanation for Sample Output 1

Troy should change the size of the 3^\text{rd} 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



There are no comments at the moment.