Fișierul intrare/ieșire	reteta1.in, reteta1.out	Sursă	ONI 2004 clasa a 8-a
Autor	Dana Lica	Adăugată de	tudor voicu • Fantastic_Man
Timp de execuție pe test	0.05 sec	Limită de memorie	2048 KB
Scorul tău	N/A	Dificultate	N/A

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Reteta1

Gigel trebuie sa cumpere n medicamente, numerotate de la 1 la n. Doctorul i-a dat m retete de doua tipuri, codificate cu numerele 1, 2 astfel:
1 – reteta necompensata, adica pretul medicamentelor de pe reteta se achita integral de catre cumparator;
2 – reteta compensata 50%, adica pretul medicamentelor inscrise pe reteta se injumatateste.

Se stie ca pe retete nu exista un alt medicament decat cele numerotate de la 1 la n si o reteta nu contine doua medicamente identice.

Daca o reteta este folosita atunci se vor cumpara toate medicamentele inscrise pe ea.

Cerinta

Scrieti un program care sa determine suma minima de bani necesara pentru a cumpara exact cate unul din fiecare dintre cele n medicamente, folosindu-se de retetele avute la dispozitie.

Date de intrare

Fisierul de intrare reteta1.in are urmatorul format:

• pe prima linie sunt scrise numerele naturale n si m;
• pe urmatoarele m linii sunt descrise cele m retete, cate o reteta pe o linie. Linia care descrie o reteta contine tipul retetei ( 1 necompensata sau 2 compensata), urmat de un numar natural q reprezentand numarul de medicamenta de pe reteta, apoi q numere distincte din multimea { 1, 2, ..., n } reprezentand medicamentele inscrise pe acea reteta;
• pe ultima linie a fisierului de intrare dunt inscrise n numere naturale separate prin cate un spatiu, reprezentand in ordine de la 1 la n, pretul medicamentelor.

Toate numerele de pe aceeasi linie sunt separate prin cate un spatiu.

Date de iesire

Fisierul de iesire reteta1.out va contine o singura linie pe care va fi scris un numar real cu o singura zecimala, reprezentand suma minima determinata.

Restrictii

• 1 ≤ N ≤ 20
• 1 ≤ M ≤ 15
• 1 ≤ pretul oricarui medicament ≤ 200
• Pentru datele de test exista intotdeauna solutie.

Exemplu

Explicatie

Solutia s-a obtinut prin folosirea primei si celei de a patra retete.
O alta solutie, dar de cost mai mare, s-ar fi obtinut daca se folosea reteta a patra si cea de a cincea.