Pe parcursul anilor în universitatea T&P (Tândală şi Păcală) au fost procurate mai multe echipamente periferice externe, care se conectează la calculator prin diferite porturi, identificate după o valoare numerică (paralel - 1, serial - 2, USB - 3, SCSI - 4, IEEE1394 - 5). Recent rectorul a decis înlocuirea tuturor calculatoarelor din universitate. Calculatoarele noi nu au toate porturile enumerate – unele porturi au fost excluse aleator pentru a micşora preţul. Din acest motiv apare problema de reconectare a echipamentelor.
Administratorul vrea să repartizeze calculatoarele astfel încât numărul echipamentelor care rămân neconectate să fie cât mai mic (sau chiar 0). El are lista calculatoarelor primite, în care pentru fiecare calculator sunt indicate porturile existente, şi lista echipamentelor, în care pentru fiecare dispozitiv sunt indicate porturile prin care se poate face conectarea la calculator. Fiecare dispozitiv se conectează la un calculator distinct şi fiecare calculator are conectat cel mult un dispozitiv extern.
Cerinţă
Scrieţi un program care va ajuta administratorul să repartizeze calculatoarele astfel încât numărul echipamentelor rămase neconectate să fie minim.
Date de intrare
Fişierul text universitate.in conţine pe prima linie trei numere întregi, separate prin spaţiu: N M K, unde N reprezintă numărul de calculatoare, M numărul de echipamente periferice, iar K numărul de porturi. Următoarele N linii conţin de la 0 la K numere, separate prin spaţiu: în linia i+1 se vor regăsi numerele porturilor, existente în calculatorul cu numărul i. Urmează M linii, care vor conţine de la 1 la K numere întregi, separate prin spaţiu: linia N+1+i va descrie numerele porturilor, prin care echipamentul i poate fi conectat la calculator.
Date de ieşire
Fişierul text universitate.out va conţine o singură linie pe care va fi scris un număr întreg – numărul minim de echipamente care nu pot fi conectate la calculatoarele noi.
Restricţii
1 < M < N < 100
0 < K ≤ 5
Exemple
universitate.in
universitate.out
Explicaţie
3 3 5
1 3 5
2 4
1 2 3 4 5
1
2
3 4
0
Vom nota C – calculator, E - echipament
Unul dintre modurile posibile de conectare ar fi
C1 E1
C2 E3
C3 E2
Toate echipamentele sunt conectate.
universitate.in
universitate.out
Explicaţie
4 3 2
1
1
2
1
2
2
1
1
E1 şi E2 pot fi conectate numai la C3. Prin urmare, unul dintre ele rămâne neconectat.
E3 poate fi conectat la oricare dintre C1, C2, C4.