Reteta

reteta

== include(page="template/taskheader" task_id="reteta") ==

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.
 
h2. 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.

Poveste si cerinta...

h2. Date de intrare

Fisierul de intrare $reteta.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.

Fisierul de intrare $reteta.in$ ...

h2. Date de iesire

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

In fisierul de iesire $reteta.out$ ...

h2. Restrictii

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

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. reteta.in |_. reteta.out |

| $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$

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|
h3. 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.

...

== include(page="template/taskfooter" task_id="reteta") ==

2742