== include(page="template/taskheader" task_id="negot") ==
Radusqrt, cel mai mare sultan al tinutului iGorj, vazand ca celorlalti sultani le place viata si ca isi doresc un numar nelimitat de neveste, a pus mare interdictie pe capul lor. Acum, fiecare sultan are voie sa aiba maxim K neveste, iar o nevasta poate fi a unui singur sultan. In tinut exista N sultani si M femei. Fiecare sultan i are o atractie pentru un numar de Ti femei.
Preavalorosul Radusqrt doreste ca alaiul sau de sultani sa fie cat mai fericit, asa ca va imparti femeile in mod optim astfel incat suma numarului de neveste a fiecarui sultan sa fie cat mai mare posibila.
Radusqrt, sultanul indepartatului tinut iGorj, a facut o analiza amanuntita a situatiei economice de pe taramul sau. In urma acestei analize, a observat ca unii dintre producatorii de matase au inceput sa aiba monopol, acaparand doar pentru ei intreaga piata. Drept urmare, Radusqrt a pus mare restrictie ca niciun producator sa nu mai poata face afaceri cu mai mult de K magazine. De altfel, niciun magazin nu va mai avea voie sa faca afaceri cu mai mult de un producator. In tinut exista N producatori si M magazine. Fiecare producator i are o relatie buna de afaceri cu un numar de Ti magazine.
Preavalorosul Radusqrt doreste ca economia tinutului sa fie cat mai prospera, asa ca va ordona el insusi pentru fiecare producator, cu ce magazine va mai face negot. Sultanul nostru va alege in mod optim, astfel incat suma numarului de magazine cu care face negot fiecare producator sa fie cat mai mare posibila, in acest mod cat mai multi supusi vor contribui la bunul mers al economiei.
Ajutati-l pe Radusqrt sa determine aceasta suma!
h2. Date de intrare
Fişierul de intrare $negot.in$ va contine pe prima linie 3 numere N, M si K (numarul de sultani, numarul de femei din tinut si numarul de neveste maxim admise per sultan); pe fiecare dintre urmatoarele N linii se vor afla un numar Ti (reprezentand pentru cate femei are sultanul i o atractie) si Ti numere, fiecare reprezentand numarul de ordine al femeii simpatizate.
Fişierul de intrare $negot.in$ va contine pe prima linie 3 numere N, M si K (numarul de producatori, numarul de magazine si numarul maxim de magazine cu care poate face negot un producator); pe fiecare dintre urmatoarele N linii se vor afla un numar Ti (reprezentand numarul de magazine cu care este in relatii bune producatorul i) si Ti numere, fiecare reprezentand numarul de ordine al magazinului.
h2. Date de ieşire
În fişierul de ieşire $negot.out$ se va afla pe prima linie un sigur numar S reprezentand suma ceruta in enunt.
În fişierul de ieşire $negot.out$ se va afla pe prima linie un sigur numar $S$ reprezentand suma ceruta in enunt.
h2. Restricţii
* $1 ≤ N ≤ 1000$ ; $1 ≤ M ≤ 40000$ ; $1 ≤ K ≤ 30$
* Pentru 10 puncte $1 ≤ N, M ≤ 5$ ; K=2
* Pentru alte 10 puncte $1 ≤ N, M ≤ 10$ ; K=3
* Pentru alte 20 puncte $1 ≤ N, M ≤ 1000$ ; K=1
* Pentru alte 30 puncte $1 ≤ N, M ≤ 1000$ ; $1 ≤ K ≤ 15$
* Se garanteaza ca un sultan iubeste maxim 200 de femei!
* Pentru $10$ puncte $1 ≤ N, M ≤ 5$ ; K=2
* Pentru alte $10$ puncte $1 ≤ N, M ≤ 10$ ; K=3
* Pentru alte $20$ puncte $1 ≤ N, M ≤ 1000$ ; K=1
* Pentru alte $30$ puncte $1 ≤ N, M ≤ 1000$ ; $1 ≤ K ≤ 15$
* Se garanteaza ca un producator este in relatii bune cu maxim 200 de magazine!
h2. Exemplu
table(example). |_. rusuoaica.in |_. rusuoaica.out |
table(example). |_. negot.in |_. negot.out |
| 3 5 2
2 1 5
3 1 2 3
h3. Explicaţie
Impartirea va fi astfel: sultan1 va lua femeile 1 si 5, sultan2 va lua femeile 2 si 3, iar sultan3 #staincasa si nu ia nici o femeie.
Impartirea va fi astfel: producator1 va aproviziona magazinele 1 si 5, producator2 va aproviziona magazinele 2 si 3, iar producator3 #staincasa si nu aprovizioneaza nici macar un magazin.
== include(page="template/taskfooter" task_id="harem") ==
== include(page="template/taskfooter" task_id="negot") ==
