Noile reguli din sistemul sanitar cer ca medicii să nu prescrie pe reţete un anumit medicament, ci să menţioneze substanţa activă. Reţeta este formată din n prescripţii, câte una pentru fiecare substanţă activă prescrisă.

Farmacista de la care cumpăr medicamentele mi-a făcut o listă în care pentru fiecare substanţă activă de pe reţetă sunt trecute medicamentele care conţin substanţa activă respectivă, precum şi preţul pastilelor prescrise din medicamentul respectiv, sub forma următoare:

• substanţa activă : medicament1 preţ1, medicament2 preţ2, ..., medicamentk preţk

Din păcate, între anumite medicamente există incompatibilităţi şi ca urmare ele nu pot fi administrate simultan, deoarece ar produce reacţii adverse. De aceea, farmacista mea mi-a dat şi o listă de incompatibilităţi, în listă fiind specificate perechi de medicamente incompatibile, sub forma:

• medicament1/medicament2

Când cumpăr reţeta, eu trebuie să iau câte un medicament pentru fiecare substanţă activă prescrisă de medic şi să am grijă să nu cumpăr medicamente care sunt incompatibile. Desigur, voi cumpăra pastilele prescrise pentru tratamentul complet.

Cerința

Cunoscând lista pe care mi-a dat-o farmacista, precum şi incompatibilităţile dintre medicamente, scrieţi un program care să determine:

1. câte medicamente am la dispoziţie pentru fiecare substanţă activă;
2. suma minimă pe care trebuie să o cheltui pentru a cumpăra reţeta.

Date de intrare

Fișierul de intrare farma.in conține pe prima linie numărul natural c, reprezentând cerinţa pe care trebuie să o rezolvăm (1 sau 2). Pe a doua linie se află numărul natural n, reprezentând numărul de substanţe active prescrise de medic. Pe următoarele n linii se află lista pe care mi-a dat-o farmacista, pe fiecare linie fiind specificată o substanţă activă, urmată de medicamentele care conţin această substanţă şi preţurile lor, sub forma precizată în enunţ. Pe următoarea linie se află un număr natural m, reprezentând numărul de perechi de medicamente existente în lista de incompatibilităţi. Pe următoarele m linii sunt scrise perechile de medicamente incompatibile, câte o pereche pe o linie, sub forma precizată în enunţ.

Date de ieșire

Dacă cerinţa este 1, fişierul de ieşire farma.out va conţine n linii, pe linia i (1≤i≤n) fiind scris numărul de medicamente disponibile pentru substanţa activă descrisă pe linia i+1 în fişierul de intrare.

Dacă cerinţa este 2, fişierul de ieşire farma.out va conţine o singură linie pe care va fi scris un număr natural reprezentând suma minimă pe care trebuie să o plătesc pentru a cumpăra reţeta, în condiţiile descrise în enunţ.

Restricții și precizări

• 0 < n < 10
• 0 ≤ m ≤ 1400
• Denumirile substanţelor active şi ale medicamentelor sunt şiruri de maximum 30 de litere mici ale alfabetului englez. Un medicament poate apărea în lista unei singure substanţe active.
• Preţurile pastilelor sunt numere naturale nenule strict mai mici decât 1000.
• Pentru fiecare substanţă activă există cel mult 9 medicamente care să conţină substanţa activă respectivă.
• În fiecare pereche din lista de incompatibilităţi se află medicamente care conţin substanţe active diferite.
• În lista de medicamente corespunzătoare fiecărei substanţe active pot exista oricâte spaţii, dar lungimea oricărei linii nu depăşeşte 700 de caractere.
• Pentru datele de test există întotdeauna soluţie.
• Pentru teste valorând 10% din punctaj cerinţa este 1.

Exemplul 1

farma.in

1
3
metformin:siofor 10,glibomet 30,bidiab 60,gliformin 10
ibuprofen:nurofen 24,advil     35,         ibusinus 9
  diclofenac : diclac 28 ,   voltaren 50, cambia 102
0

farma.out

4
3
3

Explicație

Există 4 medicamente pentru prima substanţă activă, 3 medicamente pentru cea de a doua şi tot 3 medicamente pentru cea de a treia.

Exemplul 2

farma.in

2
3
metformin:siofor 10,glibomet 30,bidiab 60,gliformin 10
ibuprofen:nurofen 24,advil 35,         ibusinus 9
  diclofenac : diclac 28 ,   voltaren 50, cambia 102
5
siofor/diclac
gliformin/diclac
ibusinus/siofor
ibusinus/voltaren
bidiab/diclac

farma.out

67

Explicație

Plătim suma minimă 67 dacă vom cumpăra glibomet (preţ 30), ibusinus (preţ 9), diclac (preţ 28).

Observaţi că oricare două medicamente cumpărate sunt compatibile.