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.

prof. Sergiu Corlat

Liceul Orizont, Chisinau

scorlat@gmail.com