== include(page="template/taskheader" task_id="drept") ==
În timpul orei de matematică, Bianca nu este atentă și începe să deseneze *N* dreptunghiuri pe caiet. La un moment dat, își pune următoarea întrebare: Care este numărul maxim de dreptunghiuri *K*, pe care poate sa le aleagă, astfel încât primul să încapă în al doilea, al doilea în al treilea,...., al [*K*]-1-lea în al [*K*]-lea? Pentru că nu știe răspunsul la această întrebare, îl roagă pe prietenul ei Ștefan să o ajute. Ștefan se gândește puțin și găsește un algoritm prin care să rezolve problema Biancăi și să afle numărul maxim. Găsiți și voi algoritmul lui Ștefan.
In timpul orei de informatica, Bianca se plictiseste si incepe sa deseneze N dreptunghiuri pe caiet. La un moment dat, isi pune urmatoarea intrebare: Care este numar maxim K de dreptunghiuri, pe care poate sa le aleaga, astfel incat primul sa incape in al doilea, al doilea in al treilea,...., al k-1-lea in al k-lea? Pentru ca nu stie raspunsul la aceasta intrebare, il roaga pe prietenul ei Stefan sa o ajute. Stefan se gandeste putin si gaseste un algoritm prin care sa rezolve problema Biancai si sa afle numarul maxim. Gasiti si voi algoritmul lui Stefan.
Se dau *N* dreptunghiuri pentru care se știe lungimea *L* și lățimea *l*. Se cere să răspundeți la întrebarea Biancăi. Se consideră că un dreptunghi *D[~1~]* cu lungime *L[~1~]* și lățime *l[~1~]* încape în alt dreptunghi *D[~2~]* cu lungime *L[~2~]* și lățime *l[~2~]* dacă *L[~1~]* < *L[~2~]* și *l[~1~]* < *l[~2~]*.
Se dau N dreptunghiuri pentru care se stie lungime L si latime l. Se cere sa raspundeti la intrebarea Biancai. Se considera ca un dreptunghi D1 cu lungime L1 si latime l1 incape in alt dreptunghi D2 cu L2 si l2 daca L1<L2 si l1<l2.
h2. Date de intrare
Fișierul de intrare $drept.in$ conține pe prima linie numărul *N* de dreptunghiuri. Următoarele *N* linii conțin 2 numere întregi ce reprezintă lungimea *L* si lățimea *l* fiecarui dreptunghi.
Fisierul de intrare $drept.in$ constine pe prima linie numarul N de dreptunghiuri. Urmatoarele N linii contin 2 numere intregi ce reprezinta lungimea L si latimea l fiecarui dreptunghi.
h2. Date de ieșire
h2. Date de iesire
În fișierul de ieșire $drept.out$ se va afișa pe primul rând numărul maxim *K* de dreptunghiuri ce pot fi alese astfel încât primul să intre în al doilea, al doilea în al treilea, ..., al [*K*]-1-lea în al [*K*]-lea.
În fisierul de iesire $drept.out$ se va afisa pe primul rand numarul maxim K de dreptunghiuri ce pot si alese astfel incat primul sa intre in al doilea, al doilea in al treile,...., al k-1-lea in al k-lea.
h2. Restricții
h2. Restrictii
* 1 ≤ *N* ≤ 100.000
* 0 ≤ *L*, *l* ≤ 1.000.000
* $1 ≤ N ≤ 100.000$
* $1 ≤ l ≤ L ≤ 1.000.000$
h2. Exemplu
table(example).
table(example).
|_. drept.in |_. drept.out |
| 7
26 12
| 4
|
h3. Explicație
h3. Explicatie
Se aleg dreptunghiurile 5,3,4,6, în această ordine.
Se aleg dreptunghiurile 3,2,4,6, in aceasta ordine.
== include(page="template/taskfooter" task_id="drept") ==
