Laiko ribojimas: 0.5s

Atminties ribojimas: 32MB

Duomenų failas: varles.in

Rezultatų failas: varles.out

Jei norite pateikti savo sprendimą - prisijunkite.

Varlės

Varlių šeimynėlė išsibarstė ant koordinačių x ašies. Motina varlė, norėdama sužinoti kaip išsibarsčiusios varlės, apibrėžė varlių išsibarstymo kriterijų kaip atstumą tarp dviejų tolimiausių varlių. Dabar jai įdomu kokią minimalią reikšmę šis kriterijus įgis.

Akivaizdu, kad šis kriterijus nuolatos keičiasi, kadangi kiekviena varlė nuo savo pradinės pozicijos juda kažkuria kryptimi vienodu greičiu.

Pradiniai duomenys

Pirmojoje eilutėje bus pateiktas varlių skaičius 1\\leqn\\leq10^5. Sekančiose n eilučių bus aprašytos pačios varlės, t.y. eilutėje i bus pateikti du tarpu atskirti sveikieji skaičiai - i'tosios varlės pozicija -10^5\\leqp_i\\leq10^5 bei varlės greitis -10^5\\leqg_i\\leq10^5.

Išvestis

Minimalus varlių išsibarstymo rodiklis.

Atsakymas bus priimtas, jei jis nuo teisingo nebus nutolęs daugiau kaip 10^{-9}.

Pavyzdžiai

Pradiniai duomenys Rezultatai 
3
-100 1
100 -1
101 -1
 
1