Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

AL_29_07 - Ostatnia runda AlgoLigi

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ń zi które przygotuje. Łącznie więc muszą przygotować X = \sum_{i = 1}^{n} z_i 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 \lceil X / k \rceil 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 <= zi <= 107 oraz liczba opanowanych przez niego działów algorytmiki 1 <= di <= k. W drugim z wierszy znajduje się di 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


Dodane przez:Adam Bąk
Data dodania:2016-08-25
Limit czasu wykonania programu:1s-2s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.