Problem G
Game Suggestions
Khadija is working on her new game, which will be a…well, she doesn’t really know yet! She has made an extremely flexible game engine, and being a skilled developer, she can implement just about anything in it.
To find out what the game should contain, she has asked her friends for input. They have a lot of suggestions. So many, in fact, that to not overwhelm her with ideas, they have promised to only present at most one suggestion each.
However, they all want to give Khadija as many different suggestions as possible, so they have gathered and found a set of suggestions such that:
-
They maximise the total number of suggestions they tell to Khadija
-
Every person suggests at most one of their own suggestions
When Khadija has received all the suggestions, she assigns them to one or more categories.
To get some variation into the game, she limits the number of suggestions from one category. She then picks as many suggestions as possible, given the category limits (A suggestion only counts towards one category).
While she’s busy implementing all these suggestions, her friends wonder how many suggestions she could’ve ended up implementing in theory.
Input
The input begins with a single line with three integers $F$, $S$ and $C$: The number of friends, distinct suggestions and distinct categories, respectively.
Next follow $F$ lines, one line for each friend: The line contains $Fn_ i$ space separated suggestion names.
Then, $C$ lines follow, one for each category. The line starts with an integer $Cn_ i$, the maximum number of suggestions Khadija wants to include that are assigned to this category, followed by $Sn_ i$ space separated suggestion names which are part of this category.
Output
Output the maximum number of suggestions Khadija could possibly end up implementing.
Limits
-
$0 < F, S, C, Fn_ i\leq 200$
-
$0 < Cn_ i \leq Sn_ i \leq 100$
-
All suggestion names are unique, and consist of between $1$ and $20$ characters in the range a–z and 0–9.
| Sample Input 1 | Sample Output 1 |
|---|---|
7 9 4 ducks 2d guns 3d swords 3d swords 3d swords wolves swords 2d zombies 2d vampires demons 2d swords 1 2d 3d 1 swords guns 1 wolves ducks 4 wolves zombies vampires demons |
5 |
