Problem E
Wedding Food
It’s your big day! You are having a wedding party, but your caterer has canceled on you last minute! In desperation, you call around to see if any restaurants nearby are able to get you the food you need. In a stroke of luck, the local pizza shop accepts to cater! You go ahead and order multiple types of pizza not knowing for sure what everyone likes.
But you know that plenty of your invitees don’t like the same type of pizzas and don’t want to make them upset. You decide to ask everyone for their preferences as they arrive and write it down. Your goal is to make everyone as happy as you can with the pizza you have. If they receive a pizza they like, it gives them $+1$ happiness. If they dislike it, it gives them $-2$ happiness. If they are indifferent, it gives them $0$ happiness.
Input
The first line of input contains two integers $N$ and $M$ ($1 \le N, M \le 100$). $N$ denotes the number of types of pizzas you ordered, and $M$ denotes the number of attendees. The following $N$ lines describe the type of pizza as a string followed by $c$ ($1 \le c \le M$), which is the amount of slices you ordered. You may assume that there is exactly one slice of pizza for every attendee. The input starts with the total number of attendees, $M$. The following $M$ lines each consist of an attendee’s name, preferred pizza type, and disliked pizza type. The data is not sorted since it was collected in the order they arrived. All pizza names consists of up to $10$ English lower or uppercase letters.
Output
Display the maximum amount of happiness that can be achieved.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 5 Sausage 2 Pepperoni 1 Cheese 2 John Sausage Cheese Mary Cheese Pepperoni Bob Sausage Pepperoni Jeff Pepperoni Cheese Abraham Sausage Cheese |
4 |
