Problem G
Gin og Tónik

Mynd eftir JIP. Leyfi CC BY-SA 4.0.

Enn og aftur er komið að árlega fundi Klúbbi Alkóhólsofnæmra Tónikdrykkjanda Thulebúa Innan Suðvesturlands (KATTIS). Félagsmeðlimir hafa ýmis sjaldgæf ofmæmi og saman prófa allskonar tónikdrykki á fundinum. Þema ársins er gamli góði kokteillinn Gin og Tónik! Sem barþjónn kvöldsins er verkefni þitt að bera fram hættulausa og bragðgóða drykki handa eins mörgum gestum og hægt er.

KATTIS meðlimir skilja hvað það getur verið mikil þraut að finna hættulausan drykk, svo þeir hafa gefið þér lista allra ofnæma þeirra fyrirfram. Þú skipulagðir þig vel og kynntir þér alla ofnæmisvalda í öllum gin og tónik drykkjunum sem klúbburinn býður upp á. Nú er spurningin: hversu margir gestir geta fengið sér kokteil hættulaust?

Input

• Ein lína með fjölda meðlima $n\in \{ 1,\ldots , 1000\} $,

• $n$ línur, ein fyrir hvern meðlim, sem gefa nafn meðlimsins, fjölda ofnæmisvalda $l\in \{ 1,\ldots , 10\} $ sem meðlimurinn er með ofnæmi fyrir, og nöfn þessarra $l$ ofnæmisvalda,

• ein lína með fjölda gina $g\in \{ 1,\ldots , 100\} $,

• $g$ línur, ein fyrir hvert gin, sem gefa nafn ginsins, fjölda eininga $u\in \{ 1,\ldots , n\} $ í boði af þessu gini, fjöldi ofnæmisvalda $l\in \{ 0,\ldots , 10\} $ í þessu gini, og nöfn þessarra $l$ ofnæmisvalda,

• ein lína með fjölda tónika $t\in \{ 1,\ldots , 100\} $,

• $t$ línur, ein fyrir hvern tónik, sem gefa nafn tóniksins, fjölda eininga $u\in \{ 1,\ldots , n\} $ í boði af þessum tónik, fjölda ofnæmisvalda $l\in \{ 0,\ldots , 10\} $ í þessum tónik, og nöfn þessarra $l$ ofnæmisvalda.

Öll nöfn samanstanda af $1$ til $10$ enskum lágstöfum a–z. Nöfn meðlima, gina, tónika og ofnæmisvalda eru öll ólík.

Output

Hámarksfjöldi gesta sem geta fengið kokteil sem samanstendur af einni einingu af gini og einni einingu af tónik án þess að neinn fái drykk með ofnæmisvalda sem þau eru með ofnæmi fyrir.

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

3
ane 1 quinine
bo 2 nuts almonds
clara 1 nuts
1
gin 2 0
1
tonic 3 0

2

2
ane 1 quinine
bo 1 almonds
1
gin 2 1 quinine
1
tonic 2 1 quinine

1