Gigel trebuie să cumpere n medicamente, numerotate de la 1 la n. Doctorul i-a dat m reţete de două tipuri, codificate cu numerele 1, 2 astfel:
1 - reţetă necompensată, adică preţul medicamentelor de pe reţetă se achită integral de către cumpărător;
2 - reţetă compensată 50%, adică preţul medicamentelor înscrise pe reţetă se înjumătăţeşte.
Se ştie că pe reţete nu există un alt medicament decât cele numerotate de la 1 la n şi o reţetă nu conţine două medicamente identice.
Dacă o reţetă este folosită atunci se vor cumpăra toate medicamentele înscrise pe ea.

Cerinţă

Scrieţi un program care să determine suma minimă de bani necesară pentru a cumpăra exact câte unul din fiecare dintre cele n medicamente, folosindu-se de reţetele avute la dispoziţie.

Date de intrare

Fişierul de intrare reteta2.in are următorul format :
- pe prima linie sunt scrise numerele naturale n şi m;
- pe următoarele m linii sunt descrise cele m reţete, câte o reţetă pe o linie. Linia care descrie o reţetă conţine tipul reţetei (1 necompensată sau 2 compensată), urmat de un număr natural q reprezentând numărul de medicamente de pe reţetă, apoi de q numere distincte din mulţimea {1, 2, ..., n} reprezentând medicamentele înscrise pe acea reţetă;
- pe ultima linie a fişierului de intrare sunt scrise n numere naturale separate prin câte un spaţiu, reprezentând în ordinea de la 1 la n, preţul medicamentelor.
Toate numerele de pe aceeaşi linie sunt separate prin câte un spaţiu.

Date de ieşire

Fişierul de ieşire reteta2.out va conţine o singură linie pe care va fi scris un număr real cu o singură zecimală, reprezentând suma minimă determinată.

Restricţii

1 <= N <= 20
1<= M <= 15
1 <= preţul oricărui medicament <= 200
Pentru datele de test există întotdeauna soluţie.

Exemple

reteta2.in	reteta2.out	Explicaţii
4 5 2 1 3 2 2 2 3 1 1 1 1 3 4 1 2 1 1 3 8 20 2 16	45.0	Soluţia s-a obţinut prin folosirea primei şi celei de a patra reţete. O altă soluţie, dar de cost mai mare, s-ar fi obţinut dacă se folosea reţeta a patra şi cea de a cincea.

autor: Prof. Dana Lica

propunător: Prof. Emanuela Cerchez

Liceul de Informatica ″Grigore Moisil″

emanuela.cerchez@gmail.com