Šeštadieninė informatikos olimpiadininkų mokykla

Kai kurie žmonės mano, kad kuo dramblys didesnis, tuo jis ir protingesnis. Norėdami tai paneigti, Jūs ėmėte nagrinėti tam tikrą dramblių aibę ir norite sustatyti į eilę kuo daugiau dramblių taip, kad jų svoriai didėtų, o intelekto koeficientai mažėtų.

Parašykite programą, sprendžiančią šį uždavinį.

Pradiniai duomenys

Pirmoje pradinių duomenų failo eilutėje įrašytas dramblių skaičius N (). Drambliai yra sunumeruoti nuo 1 iki N.

Sekančios N eilučių aprašo dramblius. Kiekvienoje eilutėje įrašyta po du sveikuosius skaičius: (i+1)-oje eilutėje pirmasis skaičius žymi i-ojo dramblio svorį kilogramais, o antrasis - jo intelekto koeficientą. Abu dramblį aprašantys skaičiai yra iš intervalo [1, 10000].

Du drambliai gali būti vienodo svorio, vienodo intelekto, arba net vienodo svorio ir vienodo intelekto.

Rezultatai

Pirmoje rezultatų failo eilutėje turi būti įrašytas vienintelis skaičius: didžiausias skaičius dramblių, kuriuos galima sustatyti į vieną eilę taip, kad jų svoriai sudarytų griežtai didėjančią progresiją, o intelekto koeficientai - griežtai mažėjančią.

Pavyzdžiai

9
6008 1300 
6000 2100 
500 2000 
1000 4000 
1100 3000 
6000 2000 
8000 1400 
6000 1200 
2000 1900

4