AlgoLiga 2018

Wszystko co dobre kiedyś się kończy. I tak nadszedł czas na zorganizowanie ostatniej rundy AlgoLigi. Organizatorzy postanowili przygotować mnóstwo zadań z różnych działów algorytmiki. Chęć udziału w przygotowaniach zgłosiło n osób. Każda z nich zadeklarowała liczbę zadań z_i które przygotuje. Łącznie więc muszą przygotować  zadań. Nie mogą one jednak być przypadkowe. Mamy k kategorii problemów, a nie każdy z autorów da radę przygotować zadanie z dowolnej tematyki. Ponadto runda powinna być zbilansowana, więc organizatorzy postanowili, aby każda kategoria zawierała co najwyżej zadań (każde zadanie dotyczy tylko jednej kategorii). Powstaje w takim razie pytanie: czy jest to możliwe, czy może runda jest skazana na porażkę już od samego początku?

Wejście

Wejście rozpoczyna liczba 1 <= k <= 1000. W kolejnych k wierszach znajdują się unikalne nazwy kategorii problemów. Każda taka nazwa składa się z małych liter alfabetu angielskiego, a jej długość nie przekracza 20 znaków. Następnie dana jest liczba 1 <= n <= 1000, po której następują opisy kolejnych autorów zadań. Pojedynczy opis składa się z dwóch wierszy. W pierwszym z nich znajdują się kolejno: nazwa autora (słowo o długości nie większej niż 20 znaków, składające się wyłącznie z małych liter alfabetu angielskiego), liczba przygotowywanych przez niego zadań 1 <= z_i <= 10⁷ oraz liczba opanowanych przez niego działów algorytmiki 1 <= d_i <= k. W drugim z wierszy znajduje się d_i różnych słów - wspomniane kategorie. Dany autor może przygotowywać zadania wyłącznie z tych działów.

Wyjście

Na wyjście należy wypisać słowo "TAK", jeśli jest możliwe przygotowanie rundy zgodnie z postanowieniami, a "NIE" w przeciwnym przypadku.

Przykład

Wejście:
7
graphs
dynamicprogramming
greedy
numbertheory
datastructures
geometry
strings
5
adambak 2 1
numbertheory
macbon 4 3
datastructures graphs greedy
kaspro 3 7
graphs dynamicprogramming greedy numbertheory datastructures geometry strings
mariosoft 3 7
graphs dynamicprogramming greedy numbertheory datastructures geometry strings
narbej 2 4
graphs greedy datastructures dynamicprogramming

Wyjście:
TAK

Wyjaśnienie do przykładu:
Autorzy mają do zrobienia 14 zadań, jest 7 kategorii więc na każdą wypadają po 2 zadania.
Możliwy podział pracy:
adambak: 2 x numbertheory
macbon: datastructures, 2 x greedy, graphs
kaspro: geometry, strings, datastructures
mariosoft: geometry, strings, graphs
narbej: 2 x dynamicprogramming