patrate1

Patrate 1

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

Anei îi place mult să se joace la calculator. Acum are un nou joc în care $n$ blocuri orizontale formate din pătrate de latură $1$ , cad pe verticală. Suprafaţa de joc se reprezintă ca un tablou cu $L$ ( $L$ > $n$ ) linii  numerotate de la $1$ la $L$ şi $C$ coloane, numerotate de la $1$ la $C$, ca în figură. Tabloul este constituit din $L$ * $C$ celule pătratice de latură $1$. Fiecare bloc este format din unul sau mai multe pătrate alăturate, situate doar pe direcţia orizontală. Blocurile sunt numerotate de la $1$ la $n$ şi  cad pe rând, în această ordine, întotdeauna de pe linia $L$, la intervale diferite de timp şi au aceeaşi viteză de cădere. Fiecare pătrat din bloc cade până la linia cu cel mai mic număr de ordine care este neocupată de un alt pătrat al unui bloc căzut anterior. Dacă nu întâlneşte un alt pătrat oprit anterior, atunci se opreşte pe linia $1$. Aşadar, pătratele din acelaşi bloc pot să se oprească pe linii diferite.

Anei îi place mult să se joace la calculator. Acum are un nou joc în care $n$ blocuri orizontale formate din pătrate de latură $1$ , cad pe verticală. Suprafaţa de joc se reprezintă ca un tablou cu $L$({$L$}>{$n$})linii  numerotate de la $1$ la $L$ şi $C$ coloane, numerotate de la $1$ la $C$, ca în figură. Tabloul este constituit din $L$ * $C$ celule pătratice de latură $1$. Fiecare bloc este format din unul sau mai multe pătrate alăturate, situate doar pe direcţia orizontală. Blocurile sunt numerotate de la $1$ la $n$ şi cad pe rând, în această ordine, întotdeauna de pe linia $L$, la intervale diferite de timp şi au aceeaşi viteză de cădere. Fiecare pătrat din bloc cade până la linia cu cel mai mic număr de ordine care este neocupată de un alt pătrat al unui bloc căzut anterior. Dacă nu întâlneşte un alt pătrat oprit anterior, atunci se opreşte pe linia $1$. Aşadar, pătratele din acelaşi bloc pot să se oprească pe linii diferite.

!problema/patrate1?poza2.bmp!

h2. Date de intrare
Fişierul de intrare $patrate1.in$ conţine:

- pe prima linie două număre naturale $n$ şi $h$ , separate printr-un spaţiu, cu semnificaţia din enunţ.
- fiecare din următoarele $n$ linii conţine câte două numere naturale $c$ şi $p$, separate printr-un spaţiu. Valorile $c$ şi $p$ de pe linia $i$ + 1 reprezintă coloana corespunzătoare primului pătrat al capătului din stânga al blocului $i$ , respectiv numărul de pătrate din bloc.

 
* pe prima linie două număre naturale $n$ şi $h$ , separate printr-un spaţiu, cu semnificaţia din enunţ.
* fiecare din următoarele $n$ linii conţine câte două numere naturale $c$ şi $p$, separate printr-un spaţiu. Valorile $c$ şi $p$ de pe linia $i$ + 1 reprezintă coloana corespunzătoare primului pătrat al capătului din stânga al blocului $i$ , respectiv numărul de pătrate din bloc.

h2. Date de ieşire

h2. Restricţii

•	$1$ ≤ $h$ < $n$ ≤ $1000$
•	$2$ ≤ $c + p$ ≤ $1.000.000.000$
•	Problema admite soluţie pentru toate datele de intrare.

* {$1 ≤ h < n ≤ 1.000$}
* {$2 ≤ c + p ≤ 1.000.000.000$}
* Problema admite soluţie pentru toate datele de intrare.

h2. Exemplu

h3. Explicaţie

În figură, numerotarea pătratelor identifică blocurile din care acestea fac parte. Zona de pătrate de lungime maximă incepe la coloana 6 şi are lungimea 3.

În figură, numerotarea pătratelor identifică blocurile din care acestea fac parte. Zona de pătrate de lungime maximă incepe la coloana $6$ şi are lungimea {$3$}.

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

3915