Lõikude tükeldamine

Arvteljel on antud $N$ positiivsete täisarvuliste koordinaatidega lõiku $[L_1, R_1]$, \ldots, $[L_N, R_N]$. Üks tükeldamis\-operatsioon asendab lõigu $[L, R]$ lõikudega $[L, M]$ ja $[M, R]$, kus $M$ on positiivne täis\-arv ja $L < M < R$. Tükeldada võib nii alguses antud kui ka eelmiste tükeldamistega saadud lõike.

Ülteme, et lõik $[A, B]$, kus $A < B$ on positiivsed täisarvud, kattub tugevalt lõiguga $[L, R]$, kui lõik $[A, B]$ katab vähemalt poole lõigu $[L, R]$ pikkusest.

Ülesanne on leida vähim võimalik lõigu $[A, B]$ pikkus, mille korral on võimalik sisendis antud $N$ lõigule rakendada $K$ tükeldamisoperatsiooni nii, et lõik $[A, B]$ kattub tugevalt kõigi $N + K$ saadud lõiguga.

Esimesel real on täisarvud $N$ ja $K$ ($1 \le N \le 10^5$, $0 \le K \le 10^{14}$).

Järgmised $N$ rida kirjeldavad lõike. Nende hulgas $i$. real on $i.$ lõigu vasaku ja parema otspunkti täisarvulised koordinaadid $L_i$ ja $R_i$ ($1 \le L_i < R_i \le 10^9$). Võib eeldada, et neile lõikudele on võimalik $K$ tükeldamisoperatsiooni rakendada. Mõned antud lõikudest võivad üksteisega täpselt kokku langeda.

Väljastada üks täisarv: eelpool kirjeldatud tugevalt kattuva lõigu $[A, B]$ vähim võimalik pikkus.