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

Imagineaza-ti ca te afli in fata jocului de Tetris. Bineinteles scopul tau este de "a sparge" toate recordurile. Dar fara un algoritm bun nu puteti face nimic.
Asa ca trebuie sa gasiti o acoperire cat mai buna a suprafetei de joc, astfel incat sa asezati piesele in ordinea aparitiei lor. Adica o piesa nu poate fi asezata pe o pozitie decat daca:

Nota. Aceasta problema a fost modificata fata de original din cauza ca versiunea anterioara era gresita. Sursele vechi nu se vor reevalua pentru ca functioneaza pe varianta incorecta.

* piesa de dinaintea ei a fost asezata
* piesa mai incape pe suprafata de joc

Joci tetris. E o tabla cu N linii si 2 coloane. Piesele sunt in forma de linie verticala, o piesa i ocupand L[i] linii pe o coloana. Piesele cad clasic. Scopul este sa alegi coloana unde vrei sa cada fiecare piesa. Jocul se termina fie cand vrei tu fie cand urmatoarea piesa nu mai poate fi pusa in tabla integral.

Piesele sunt plasate intr-o anumita pozitie fiind lasate sa cada libere de undeva de deasupra suprafetei de joc.
Pentru simplificare, consideram ca piesele sunt de forma patrata.

O piesa nu poate fi folosita decat daca toate piesele dinaintea ei au fost asezate pe tabla in mod corect.
 
h2. Cerinta
 
Gasiti toate configuratiile (a, b, c) care se pot obtine. a reprezinta inaltimea primei coloane ocupate in tabla iar b inaltimea celei de a doua; c reprezinta cate piese am pus.

h2. Date de intrare

Fisierul de intrare $tetris.in$ contine pe prima linie numarul $n$ de linii si numarul $m$ de coloane ale suprafetei de joc, despartite printr-un spatiu. Apoi, pe linia a doua se vor specifica laturile fiecarui patrat in ordinea aparitiei lor. Linia se va termina cu un {$0$}.

Fisierul de intrare $tetris.in$ contine pe prima linie numarul $N$ de linii si numarul de piese $K$. Pe liniile urmatoare sunt $K$ numere L[i].

h2. Date de iesire

Fisierul de iesire $tetris.out$, contine pe prima linie numarul maxim de patrate acoperite din suprafata de joc. Pe urmatoarele linii va fi afisata suprafata de joc sub forma unei matrici, unde fiecare patrat este marcat prin numarul de aparitie. Pozitiile neocupate sunt marcate prin numarul {$0$}. Nu este obligatoriu ca toate patratele sa fie asezate.

Fisierul de iesire $tetris.out$, contine pe prima linie numarul cerut.

h2. Restrictii

* Toate numerele din fisierul de intrare sunt mai mici decat $30$

* 1 ≤ N ≤ 2.000
* 1 ≤ K ≤ 500
* 1 ≤ L[i] ≤ N

h2. Exemplu
table(example). |_. tetris.in |_. tetris.out |
|4 4

1 2 2 1 2 1 2 0
|15
6 0 3 3
5 5 3 3
5 5 2 2
1 4 2 2
|

2
2
2
2
| 9
|
h3. Explicatie
 
(0, 0), (2, 0), (4, 0), (0, 2), (2, 2), (4, 2), (0, 4), (2, 4), (4, 4)

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

 
 
==SmfTopic(topic_id="2214")==

2214