== 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.
Î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 in 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.
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 știe lungimea *L* si latimea *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~]* daca *L[~1~]* < *L[~2~]* și *l[~1~]* < *l[~2~]*.
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.
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 fișierul de ieșire $drept.out$ se va afișa pe primul rand numarul maxim K de dreptunghiuri ce pot fi 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$
* $0 ≤ 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 5,3,4,6, in aceasta ordine.
== include(page="template/taskfooter" task_id="drept") ==
