reteta

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 numeroatete 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 reteta.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ă, $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, \dots, 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 reteta.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 și precizări

• $1 \leq N \leq 20$
• $1 \leq M \leq 15$
• $1 \leq$ preţul oricărui medicament $\leq 200$
• Pentru datele de test există întotdeauna soluţie.

Exemplu

reteta.in

4 5
2 1 3
2 2 2 3
1 1 1
1 3 4 1 2
1 1 3
8 20 2 16

reteta.out

45.0

Explicație

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