h2. Date de intrare

Pe prima linie in fisierul de intrare sobo.in se afla numerule $N$, $L$ separate prin cate un spatiu reprezentand numarul de sobolani si lungimea hartilor genetice ale acestora. Pe urmatoarele $N$ linii se afla cate un sir de $L$ biti (nedespartiti de spatii) reprezentand harta unui sobolan. Pe ultima linie se afla $L$ numere separate prin spatii reprezentand costul raspunsului pentru fiecare pozitie.

Pe prima linie in fisierul de intrare $sobo.in$ se afla numerele $N$, $L$ separate prin cate un spatiu reprezentand numarul de sobolani si lungimea hartilor genetice ale acestora. Pe urmatoarele $N$ linii se afla cate un sir de $L$ biti (nedespartiti de spatii) reprezentand harta unui sobolan. Pe ultima linie se afla $L$ numere separate prin spatii reprezentand costul raspunsului pentru fiecare pozitie.

h2. Date de iesire

* $1 ≤ N ≤ 15$
* $1 ≤ L ≤ 1000$

* Costurile raspunsurilor sunt numere intregi din intervalul $[1, 1 000 000]$

* Costurile raspunsurilor sunt numere intregi din intervalul $[1, 11.000.000]$

* Nu exista sobolani cu harti genetice identice
h2. Exemplu

table(example). |_. algola.in |_. algola.out |

table(example). |_. sobo.in |_. sobo.out |

| 4 3
101
000

Costul minim 13 (in cel mai defavorabil caz) este obtinut astfel: Gigel intreaba care este valoarea hartii sobolanului inteligent in pozitia 2 si Petrica ii raspunde 1 acesta fiind cel mai defavorabil caz (daca raspunsul lui Petrica ar fi fost 0 urma intrebarea lui Gigel despre valoarea in pozitia 1 si sobolanul ar fi fost identificat cu un costul 6 + 2 = 8). Asadar niciunul dintre primii doi sobolani nu este cel inteligent. Gigel mai trebuie sa afle care din ultimii doi sobolani este cel inteligent si mai cere informatii despre pozitia 3 din harta sobolanului inteligent. Indiferent de raspuns sobolanul inteligent va fi descoperit.

==Include(page="template/taskfooter" task_id="sobo")==

==Include(page="template/taskfooter" task_id="sobo")==
 
 
 

138