Problem G
Gin and Tonic
Languages
da
en
is
It’s time once again for the annual gathering of the Club of Allergic Tonic Tasters in Scrollbar (CATTIS). Club members with various rare allergies come together to sample a range of delicious tonic-based beverages. This year’s theme centers around the timeless highball cocktail—tonight, it’s all about the classic Gin and Tonic! As the bartender for the evening, your mission is to serve safe and delightful drinks to as many guests as possible.
CATTIS members understand the challenge of finding a safe drink, so they’ve provided you with a list of their allergies in advance. You’ve done your homework, too, by familiarizing yourself with the allergens in each of the various gins and tonics available at the Club. Now, the question is: how many guests can enjoy a safe cocktail?
Input
-
One line with the number $n\in \{ 1,\ldots , 1000\} $ of members,
-
$n$ lines, one for each members, each consisting of the member’s name, the number $l\in \{ 1,\ldots , 10\} $ of allergens that this member is allergic to, and $l$ allergens’ names,
-
one line with the number $g\in \{ 1,\ldots , 100\} $ of gins,
-
$g$ lines, one for each gin, each consisting of the gin’s name, the number $u\in \{ 1,\ldots , n\} $ of available units of this gin, the number $l\in \{ 0,\ldots , 10\} $ of allergens in this gin, and the $l$ allergen’s names,
-
one line with the number $t\in \{ 1,\ldots , 100\} $ of tonics,
-
$t$ lines, one for each tonic, each consisting of the tonic’s name, the number $u\in \{ 1,\ldots , n\} $ of available units of this tonics, the number $l\in \{ 0,\ldots , 10\} $ of allergens in this tonic, and the $l$ allergen’s names.
All names consist of $1$ to $10$ lower-case letters a–z. The names of members, gins, tonics, and allergens are all different.
Output
The maximum number of guests that can receive a cocktail conisting of one unit of gin and one unit of tonic without anyone being exposed to any allergen they are allergic to.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 ane 1 quinine bo 1 almonds clara 1 nuts 2 beefeater 1 1 almonds gordons 1 2 nuts quinine 2 schweppes 1 1 nuts fentimans 1 2 almonds quinine |
2 |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 ane 1 quinine bo 2 nuts almonds clara 1 nuts 1 gin 2 0 1 tonic 3 0 |
2 |
| Sample Input 3 | Sample Output 3 |
|---|---|
2 ane 1 quinine bo 1 almonds 1 gin 2 1 quinine 1 tonic 2 1 quinine |
1 |
