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.|

GOLEBIE - Gołębie

RNO bardzo nie lubi gołębi. Każdego ranka gdy patrzy przez okno, widzi je jak sobie siedzą na gałęziach drzew i wiadomo co robią na przechodniów. Pewnego dnia postanowił raz na zawsze skończyć z nimi. Zadzwonił do swoich kolegów, którzy mieszkają w tym samym bloku co on i umówił się na pewną akcję. Wszyscy koledzy mają broń pneumatyczną :-). RNO, oczywiście, też ma broń.

Wbrew pozorom RNO jest bardzo łagodny i nie chce robić masakry na osiedlu. Jak zwykle postawił sobie pewien cel optymalizacyjny. Chce zużyć jak najmniej pocisków, jednocześnie zabijając jak najwięcej gołębi. Aby nie było sytuacji, w której strzał jednego kolegi płoszy gołębie drugiemu, wszyscy mają za zadanie strzelić (o ile mają w ogóle strzelać) w tym samym momencie. Sygnał poda RNO przez krótkofalówkę.
Każdy gołąb otrzymał od RNO unikatowy numer ze zbioru {1,2,...,m}. Koledzy zajęli już swoje pozycje i przekazali RNO numery gołębi, które są w stanie ustrzelić.

RNO zastanawia się ile gołębi może ustrzelić wraz z kolegami, gdyż nie ma sensu robić hałasu jeśli możliwe jest ustrzelenie zbyt małej liczby gołębi. Lepiej bowiem poczekać i .....

Zadanie

Twoim zadaniem jest obliczenie maksymalnej liczby gołębi, jakie może utrzelić RNO wraz z kolegami.

Wejście

W pierwszym wierszu dane są dwie liczby n,m oddzielone pojedynczym odstępem (1≤n,m≤5000), oznaczające liczbę osób które mają broń (RNO jest wśród nich) oraz liczbę gołębi. Następnie podane są numery gołębi, które mogą ustrzelić poszczególne osoby. W i+1-szym wierszu znajduje się lista numerów gołębi, które może ustrzelić osoba z numerem i. Każda lista podana jest w następujący sposób. Pierwsza liczba całkowita ni mówi ile jest w niej numerów; następnie znajduje się ni numerów gołębi.

Wyjście

Na wyjściu wypisz tylko jedną liczbę, mówiącą ile co najwyżej gołębi można ustrzelić przy założeniu, że każda osoba strzela co najwyżej jednym pociskiem (jeden strzał zabija tylko jednego gołębia).

Przykład

Dla danych wejściowych

4 5
3 1 2 3
2 1 5
3 1 2 3
3 1 3 4

poprawną odpowiedzią jest

4

Na przykład osoba nr 1 strzela do gołębia 1, osoba nr 2 strzela do gołebia nr 5, osoba nr 3 strzela do gołębia nr 2, a osoba nr 4 strzela do gołębia z numerem 3. W ten sposób przeżyje tylko jeden gołąb --- ten z numerem 4. Trudno.

Przykład 2

Dla danych wejściowych

2 1
1 1
1 1

poprawną odpowiedzią jest

1

Nie ma sensu aby obie osoby strzelały do tego samego gołębia. Wystarczy, że RNO załatwi tę sprawę indywidualnie.


Dodane przez:Rafał Nowak
Data dodania:2008-01-24
Limit czasu wykonania programu:0.168s-0.500s
Limit długości kodu źródłowego10000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ERL GOSU JS-RHINO NODEJS PERL6 VB.NET
Pochodzenie:Własne

ukryj komentarze
2011-08-20 09:50:23 Sebastian Nowak
Bo nie umiesz kodzić HK :< Mój kod w tamtym zadaniu działa 1.35s
2011-08-20 08:10:17 Krzysztof Lewko
Dlaczego HK na tym zadanku dostaje TLE?
Te same algo użyłem http://www.spoj.pl/problems/MATCHING/ tutaj, z czasem ~2.7s, a tutaj TLE, hmm

Ostatnio edytowany: 2011-08-20 08:42:42
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.