Laiko ribojimas: 1s

Atminties ribojimas: 256MB

Duomenų failas: plesikai.in

Rezultatų failas: plesikai.out

Jei norite pateikti savo sprendimą - prisijunkite.

Plėšikai

Neatmenamais laikais du didžius Labaitolistano miestus jungė Didysis prekybos kelias. Jame „dirbo” N plėšikų gaujų. Pagal seną paprotį i-oji gauja kontroliavo kelio atkarpą nuo a_i-ojo iki b_i-ojo km, apiplėšdama ja keliaujančius pirklius. Nors ir nebuvo taip, jog viena gauja būtų apglėbta kitos gaujos (žinome, jog nėra tokių skirtingų i ir j, kad a_i\\leqa_j ir b_j\\leqb_i), tačiau tose vietose, kur gaujų valdos persidengdavo, kartais įsižiebdavo kruvinos kovos. Gaujų vadai nusprendė, jog tai turi baigtis. Jie nutarė persiskirstyti savo valdas taip, kad:

1) naujieji intervalai nepersikirstų (kad nebebūtų kruvinų kovų);
2) kiekvienos gaujos naujasis intervalas priklausytų senajam (kad būtų laikomasi papročių);
3) visi intervalai būtų vienodo ilgio (sąžiningumo vardan).

Koks galėjo būti ilgiausias gaujos valdomas intervalas po persiskirstymo?

Pradiniai duomenys

Pirmoje eilutėje yra gaujų skaičius N(1\\leqN\\leq100~000). Kiekvienoje iš tolesnių N eilučių yra po du skaičius, aprašančius gaujos valdomą intervalą prieš perskirstymą (0\\leqa_i<b_i\\leq1~000~000).

Rezultatai

Išveskite didžiausią galimą gaujos valdomo intervalo ilgį po persiskirstymo kaip racionalųjį skaičių – nesuprastinamą trupmeną p/q.

Pavyzdžiai

Pradiniai duomenys Rezultatai 
3
2 6
1 4
8 12
 
5/2