Fișierul intrare/ieșire	drept.in, drept.out	Sursă	ad-hoc
Autor	din folclor	Adăugată de	Ioana Bica • ioanab
Timp de execuție pe test	0.2 sec	Limită de memorie	65536 KB
Scorul tău	N/A	Dificultate	2

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Dreptunghiuri

Î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.

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₁ cu lungime L₁ și lățime l₁ încape în alt dreptunghi D₂ cu lungime L₂ și lățime l₂ dacă L₁ < L₂ și l₁ < l₂.

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.

Date de ieșire

Î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.

Restricții

• 1 ≤ N ≤ 100.000
• 0 ≤ L, l ≤ 1.000.000

Exemplu

Explicație

Se aleg dreptunghiurile 5,3,4,6, în această ordine.