Laiko ribojimas: 1s

Atminties ribojimas: 16MB

Duomenų failas: drambliai.in

Rezultatų failas: drambliai.out

Jei norite pateikti savo sprendimą - prisijunkite.

Didesnis - gudresnis?

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

img

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

Pradiniai duomenys

Pirmoje pradinių duomenų failo eilutėje įrašytas dramblių skaičius N (1\\leN\\le1000). 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

Pradiniai duomenys Rezultatai Paaiškinimas
9
6008 1300 
6000 2100 
500 2000 
1000 4000 
1100 3000 
6000 2000 
8000 1400 
6000 1200 
2000 1900
4
Į vieną eilę galima sustatyti (iš eilės) ketvirtą, penktą, devintą ir septintą dramblius.